백준 9663 (N-Queen) c++

문제

9663번: N-Queen

n * n 체스판이 있을 때 한 칸씩 퀸이 들어가 n개의 퀸이 서로 공격하지 않을 경우의 수를 구하는 문제입니다.

퀸은 가로, 세로, 대각선 모두 이동 가능합니다.

이는 backtracking 기법으로 해결 가능합니다. 

먼저 첫번째 칸에 퀸을 두고 두번째 칸에 체스를 두면서 서로 평행하거나 대각선에 걸리면 나머지 경우는 볼 필요가 없으므로 무시해주면 됩니다.

n = 4

다음과 같은 경우는 퀸이 모두 공격하지 않으므로 가능합니다.

이는 퀸 배열을 통해서 나타낼 수 있습니다. 

queen[n] 을 선언할 때 위의 그림에서는 1, 3, 0, 2 가 됩니다.

 

재귀함수로 나타내면

void recursion(int idx) {
	if (idx == n) {
		ans++;
		return;
	}
	for (int i = 0; i < n; i++) {
		bool flag = true;
		for (int j = 0; j < idx; j++) {
			if (i == queen[j] || abs(i - queen[j]) == idx - j) {
				flag = false;
				break;
			}
		}
		if (flag) {
			queen[idx] = i;
			recursion(idx + 1);
		}
	}
}

변수 idx 는 현재 보고있는 행을 나타냅니다. 따라서 idx==n 일경우 모든 조건을 다 만족시켰다는 의미로 ans값을 1 더해주고 return해줍니다.

변수 i는 idx행의 열의 번호를 가리킵니다. 0번째, 1번째 .... n-1번째까지 반복하면서 탐색합니다.

 

 

변수 j는 idx행 전까지의 0부터 idx-1 까지의 행을 의미합니다.

if (i == queen[j] || abs(i - queen[j]) == idx - j) {
	flag = false;
		break;
}

위의 코드는 조건을 만족하지 않을 때 무시하기 위한 코드 입니다.

i == queen[j] 는 서로 평행할때를 의미합니다.

이제 대각선일때도 무시하여야 합니다.

두 점이 대각에 있다는 의미는 

왼쪽의 그림처럼 빨간색 선과 파란색 선의 길이가

동일하다는 의미입니다.

따라서 abs(i-queen[j]) == idx-j 가 만족하면

대각선에 있다는 의미입니다.

 

 

 

 

---

전체코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int ans;
int queen[16];
int n;
void recursion(int idx);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;

	recursion(0);

	cout << ans;
	return 0;
}
void recursion(int idx) {
	if (idx == n) {
		ans++;
		return;
	}
	for (int i = 0; i < n; i++) {
		bool flag = true;
		for (int j = 0; j < idx; j++) {
			if (i == queen[j] || abs(i - queen[j]) == idx - j) {
				flag = false;
				break;
			}
		}
		if (flag) {
			queen[idx] = i;
			recursion(idx + 1);
		}
	}
}