https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제분석
백준 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;
}'알고리즘 & Problem Solving' 카테고리의 다른 글
| 백준 16563번 어려운 소인수 분해 문제와 내 오개념 (0) | 2019.11.14 |
|---|---|
| 백준 2529번 부등호 문제 풀이 (0) | 2019.11.12 |
| 백준 17825번 주사위 윷놀이 문제 풀이 (2) | 2019.10.25 |
| 백준 17822번 원판 돌리기 문제 풀이 (3) | 2019.10.23 |
| Google Kickstart Round G 2019 후기 (2) | 2019.10.20 |
