백준 9663번 문제 N-Queen 문제 풀이

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

9663번: N-Queen

 

문제분석

백준 9663번 N-Queen 문제입니다. 굉장히 유명한 문제 중 하나입니다.

 

완전탐색으로 풀 수 있는것으로 알려져있습니다.

 

N이 15인데, 그러면 체스 말 판이 15x15=225칸이 있고, 이 중 15칸을 고른다고 하면

 

경우의 수가 //(\scriptstyle 225\textstyle C\scriptstyle 15//) 가 되는데, 뭐, 대충 계산해봐도

 

1억이라는 수를 훌쩍 넘는 것을 알 수 있습니다. //(100^{10}//)라고만 봐도 //(10^{20}//)이 되니깐, 1억이 //(10^8//)인 것을 감안하면 안되는 경우의 수가 되지요.

 

여기서 무조건 아닌 수를 조금 줄여보도록 하면,

 

퀸이 같은 행이나 열에 있으면 공격할 수 있으므로 각자 다른 열이나 행에 두어야 합니다.

 

그러면 NxN의 체스판에 퀸을 N개를 두려면 1행에 있는 퀸, 2행에 있는 퀸... N행에 있는 퀸이 최대 1개씩 밖에 있을 수 없습니다.

 

그리고 열에도 퀸은 최대 1마리만 둘 수 있기 때문에 이 조건을 맞추어 퀸을 배열하는 경우의 수는

 

1부터 N까지의 수를 한 줄로 나열하는 경우의 수와 같다고 볼 수 있습니다.

 

즉 //(N!//)이 되지요.

 

예를들어 //(N=4//)이고 //(1,3,2,4//)와 같이 배열한다는 것은 퀸을 (1,1), (2,3), (3,2), (4,4)에 배열한다는 뜻으로 볼 수 있습니다.

 

 

 

여기서 //(N=15//)일 때 //(15!=1307674368000//)인데 이 수도 여전히 큽니다.

 

하지만 퀸을 배치하다가 대각선으로 서로 공격할 수 있는 경우, 더이상 탐색하지 않는 가지치기(pruning)을 적용을 하면 저 수 보다는 적은 수의 탐색으로 경우의 수를 모두 찾아 볼 수가 있습니다.

 

구현전략

일단 완전탐색 문제이므로 제귀를 활용한 dfs로 탐색을 하면 쉽게 구현을 할 수 있습니다.

 

N개의 수를 나열하는 문제에 + 퀸이 대각선으로 공격할 수 있다는 점을 체크를 해야 합니다.

 

같은 대각선에 있는 좌표는 x좌표+y좌표의 값이 같거나, x좌표-y좌표의 값이 같습니다. 

 

이게 왜 그런가 하는지는 엑셀 등에 직접 좌표마다 값을 구해서 눈으로 보면 간단하며,

 

1차함수의 그래프를 그려봐도 마찬가지로 쉽게 알 수 있습니다.

 

x+y=k의 그래프를 그리면 2차원 좌표계에서 좌측상단에서 우측하단으로 뻗는 직선의 그래프를 확인할 수 있습니다.

x-y=k의 그래프 역시 2차원 좌표계에서 우측상단에서 좌측하단으로 뻗는 직선의 그래프를 확인할 수 있습니다.

 

이러한 점을 고려해서 제귀로 구현하면 생각보다 간단하게 구현할 수 있습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
/*
N=15일때
좌표계가 (0,0) ~ (14,14)라고 볼때,
*/
int pl[35]; // 0 ~ 28
int mi[35]; // 14 ~ -14
bool num[15];
int val[15];
int ans;
int n;
void dfs(int x) {
	if (x == n) {
		ans++;
		return;
	}
	for (int y = 0; y < n; y++) {
		if (num[y] == false && pl[x+y] == false && mi[x-y+14] == false) {
			val[x] = y;
			num[y] = pl[x + y] = mi[x - y + 14] = true;
			dfs(x + 1);
			num[y] = pl[x + y] = mi[x - y + 14] = false;
		}
	}
}
int main() {
	cin >> n;
	dfs(0);
	cout << ans << endl;
}