[C++] 백준 9663번 : N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

---

문제 풀이

 같은 열, 행, 그리고 대각선에 위치하면 안 되기 때문에 함수로 위치할 수 있는지 체크한다.

좌표에 놓여있을 때, (A, B)와 (X, Y)가 같은 대각선 상에 위치한다면 A - X = B - Y이다.

그리고 col 배열의 값은 x 축, col 배열의 인덱스는 y축을 나타내는 점을 이용해서 배열에 값이 입력됐다면 해당 인덱스에 값이 위치할 수 있는지 여부를 함수로 체크하고 재귀 함수를 다시 불러온다. 

느낀 점

 처음에는 되게 어려운 문제로 생각했다. 2차원 배열을 구현해서 풀어볼까도 생각했고 여러 가지로 많이 고민했는데 "(A, B)와 (X, Y)가 같은 대각선 상에 위치한다면 A - X = B - Y이다."를 알게 되고 되게 문제가 쉬워졌다. 

코드

#include <iostream>

using namespace std;

int col[16] = { 0, };
int ans = 0;
int n;

bool check(int n) {
	for (int i = 0; i < n;i++) { // col[i] : x좌표 / i : y좌표
		if (col[i] == col[n] || abs(col[n] - col[i]) == n - i) return false;
	}
	return true;
}

void n_queen(int cnt) {
	if (cnt == n) ans++;
	else {
		for (int i = 0; i < n;i++) {
			col[cnt] = i;
			if (check(cnt)) n_queen(cnt + 1);
		}
	}
}

int main() {
	cin >> n;
	n_queen(0);
	cout << ans;
}