N-Queen (feat. 백준, 9663번)

N-Queen
https://www.acmicpc.net/problem/9663

9663번: N-Queen

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/9663
#include <iostream>
using namespace std;
int N, ans;
int chk[15];
bool check(register int& x) {
	for (register int i = 1; i < x; ++i) {
		if (chk[i] == chk[x] || abs(chk[x] - chk[i]) == x - i)// 대각선이거나 같은 라인
			return false;
	}
	return true;
}
void dfs(register int ix, register int count) {
	if (count == N) {
		++ans;
		return;
	}
	for (register int y = 1; y <= N; ++y) {
		chk[ix] = y;
		if (check(ix))
			dfs(ix + 1, count + 1);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	for (register int i = 0; i < 15; ++i)
		chk[i] = 0;
	ans = 0;
	cin >> N;
	dfs(1, 0);
	cout << ans;
	return 0;
}
// *&)*@*

행 중 하나를 선택하게 되면 해당 행에는 퀸이 올 수 없습니다. (서로 공격할 수 있기 때문입니다.)

따라서 다음 행으로 옮기고 열을 차례대로 비교한다면 모든 경우의 수를 구할 수 있습니다.