<Baekjoon> #9663 DFS_nQueen c++

#9663 N-Queen
참고1, 참고2

n Queen Problem 은 대표적인 Backtracking의 예제라고 한다.

처음에는 단순하게 NxN 체스판 위의 모든 좌표에 대해 한 좌표를 기준으로 x축, y축, 대각선을 모두 구하는 방법으로 해야 하나 했다..

for (int i=0; i<n; i++) {
	queen[y][i]==visited;
    queen[i][x]==visited;
}
+모든 대각선 경우의 수 =visited

그래서 여러 블로그를 보고 공부한 결과
한 행에는 한 개의 Queen만 들어갈 수 있다는 점을 고려하여 크기가 N인 일차원 벡터를 만든다.
즉, vector<int>queen(n)을 만들었을 때 queen[i]의 값은 i행에 몇 번째 열에 queen이 들어가 있는가 이다.
아래와 같을 때, queen[0]=1, queen[1]=3, queen[2]=0, queen[3]=2

처음 행에 퀸을 놓고 나면 그 다음 행에 놓을 수 있는 퀸은 처음 퀸과 행과 행과 열이 겹치지 않아야 하고 대각선이 겹치지 않아야 한다.

일차원 벡터를 이용하여 각 행의 몇 번째 열에 퀸을 놓는 지를 저장하기 때문에 행은 겹치지 않고 열을 겹치지 않게 하는 방법은 이때까지 queen에 저장된 값이 지금 내가 넣으려는 값과 겹치지 않으면 된다.
그렇다면 다음으로 대각선을 겹치지 않게 놓는 방법을 알아야 한다.

좌표 (x,y)의 대각선 위에 있는 좌표 (a,b)는 반드시 x-a=y-b를 만족한다.
e.g. (0,1)을 기준으로 대각선에 있는 점들 (1,2), (2,3)은 반드시 (0-1)=(1-2)=-1, (0-2)=(1-3)=-2를 만족한다.

k번 째 퀸을 놓으려고 할 때 유효성 검사

bool check(int k) {
	for (int i = 0; i < k; i++)
		if (queen[i] == queen[k] || abs(queen[i] - queen[k]) == k - i)
			return false;
	return true
}

• queen[i]==queen[k] 같은 열에 들어가는 경우
• abs(queen[i] - queen[k]) == k - i
(i, queen[i])의 대각선 위에 좌표 (k, queen[k])가 있는 경우

설명하려고 하다보니 더 복잡해진 거 같다..
코드를 보면서 이해하는 게 더 빠르겠다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int MAX = 15;
vector<int> queen;
int n;
int cnt=0;
bool check(int k) {
	for (int i = 0; i < k; i++)
		if (queen[i] == queen[k] || abs(queen[i] - queen[k]) == k - i)
			return false;
	return true;
}
void nQueen(int k) {
	if (k == n) {
		cnt++; return;
	}
	for (int i = 0; i < n; i++) {
		queen[k] = i;
		if (check(k))
			nQueen(k + 1);
	}
}
int main() {
	cin >> n;
	queen = vector<int>(n);
	nQueen(0);
	cout << cnt << endl;
	return 0;
}