백준/9663/백트래킹/N-Queen

백준/9663/백트래킹/N-Queen
백트래킹을 이용한 문제로 각 행을 내려갈때마다 해당 위치에 퀸을 놓을 수 있을지 없을지를 검사하는 방법을 사용했다.

위와 같이 cur에 현재 위치에 표시를 했을 경우 다음 칸으로 넘어가니 일단 행은 검사할 필요가 없습니다.

위와 같이 이미 놓여있는 퀸에 대각선과 열을 검사하면됩니다.

이를 세가지 bool 배열을 이용하여 관리하여 퀸을 각 행에 queen을 놓아주고 만약 마지막까지 queen을 놓지 못하고 해당 재귀가 return 되었을 경우에는 해당 자리가 알맞지 않다는 소리이니 전에 재귀로 돌아가 다른 자리를 검사해봅니다.

풀이

1.첫번째풀이(퀸을 놓은 배열도 표시)

#include<iostream>
using namespace std;

int N;
int board[15][15];
bool vertical[15];
bool diagonal[29];
bool diagonal_2[29];
int result;

void func(int cur) {
	if (cur == N) {
		result += 1;
		cout << '\n';
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cout << board[i][j];
			}
			cout << '\n';
		}
	}
	for (int i = 0; i < N; i++) {
		if (vertical[i] || diagonal[cur - i + N - 1]||diagonal_2[cur+i])
			continue;
		vertical[i] = true;
		diagonal[cur - i + N - 1] = true;
		diagonal_2[cur + i] = true;
		board[cur][i] = 1;
		func(cur + 1);
		board[cur][i] = 0;
		vertical[i] = false;
		diagonal[cur - i + N - 1] = false;
		diagonal_2[cur + i] = false;
	}
}

void solution() {
	cout << result << '\n';
}

int main(void) {
	cin >> N;
	func(0);
	solution();
}