백준 9663번: N-Queen (C++)

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

9663번: N-Queen

 

퀸은 놓여있는 위치의 행과 열 그리고 대각선 두 방향을 공격할 수 있다.

 

N이 15 정도밖에 되지 않기 때문에 백트래킹을 해도 충분하다.

 

먼저 행당 1개의 퀸이 있는 것은 당연하다.

 

따라서 우리는 특정 열에 퀸을 놓을 수 있는가, 특정 대각선에 퀸을 놓을 수 있는가를 관리해주면 된다.

 

#include<iostream>
using namespace std;
int n;
bool isused[3][40];
int cnt = 0;
void func(int k) {
	//k-1개 까지 다 놓은 상태
	if (k == n + 1) {
		cnt++;
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (isused[0][i] || isused[1][k + i] || isused[2][k - i + n - 1])
			continue;
		isused[0][i] = true;
		isused[1][k + i] = true;
		isused[2][k - i + n - 1] = true;
		func(k + 1);
		isused[0][i] = false;
		isused[1][k + i] = false;
		isused[2][k - i + n - 1] = false;
	}
}
int main(void) {
	cin >> n;
	func(1);
	cout << cnt;
	return 0;
}