무슨 문제인가
유명한데 풀라하면 잘 못푸는 그런문제가 아닐까싶다.
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
퀸은 가로, 세로, 대각선으로 이동하면서 공격할 수 있다.
이를 염두에두고 한번 풀어보자
기본가정
-
같은 행(row)에는 퀸을 놓을 필요가 없다. 즉 한 row에 배치가 되는 순간 바로 다음 row로 넘어간다.
-
같은 열(col)체크를 하고, 대각선 체크를 한다.
문제풀이
4*4격자가 있다고 가정하면 거기서 column 방향, 즉 세로방향으로 한칸씩 내려가면서 검증을 할 것이다.
bool valid(int level) {
for (int i = 0; i < level; i++) {
if (col[i] == col[level] || abs((col[level] - col[i]) == level - i)) return false;
}
return true;
}col check
col[i]는 i번째 행에서 퀸이 있는 열의 위치이다.
col[k]는 k번째 행에서 퀸이 있는 열의 위치이다.
따라서, col[i] == col[k]가 성립하면, 같은 열에 퀸이 있다, 즉 세로줄 공격이 가능해진다는 뜻이다. 따라서 성립할 수 없다.
대각선 check
abs((col[level] - col[i]) == level - i)왼쪽에서 오는 공격의 경우 열에서의 차이는 행에서의 차이와 같다.
반대로 오른족은 차이의 마이너스와 같다. 따라서 대각선으로 이를 판단해야한다.
nqueen
void nqueen(int k) {
if (k == n) {
total++;
} else {
for (int i = 0; i < n; i++) {
col[k] = i;
if (valid(k)) nqueen(k+1));
}
}k는 놓아야하는 말의 번호이다. 0번부터 시작한다.
0번째 column 0번 row에서 시작한다.
우선 k == n이 달성되면, 끝에 도달했다는 뜻이다. 따라서 경우의 수를 하나 늘린다.
그렇지 않은 경우는, row의 어느 column에 놔야하는지 판단하기 시작한다.
-
시작할떄는 0번째 row, 0번 column에서 시작한다.
valid(k)에 전혀 문제가 없다. 따라서 col[0] = 0이 되고, nqueen(1)이 수행된다. -
col[1] = 0을 valid 체크한다.
즉, 1번 행에서 0번째에 퀸이 위치한다는 뜻이다.
이에 valid(1)이 수행된다.
valid(1)은 col[0] == col[1] / 0 == 0이 성립하게 되고, 따라서 false가 나온다. - false가 나왔으니, 더 진행하지 않고 루프를 한번 더 돌린다.
col[1] = 1이 되었다.
즉, 1번째행에서 1번째 col에 퀸이 위치하는것이다.
이를 또 valid(1)해보면,
col[1] - col[0] == 1 - 0 이 참이 된다. 따라서 false이다.-
col[1] = 2는 성립한다. 이제 col[2]로 넘어갈 수 있다.
-
2번째 row의 그 어떤 col에도 들어갈 수가 없다. 따라서 nqueen(3)은 진행되지 못하고 그대로 이전함수로 돌아가게 된다.
-
이상황까지오면,
col[0] = 0;
col[1] = 3;
이 된다.이런식으로 계속 반복하고 k == n 에서 total을 늘리면 된다.
정답 코드
#include <iostream>
#include <algorithm>
#define MAX 15
using namespace std;
int n, total = 0;
int col[MAX];
void nqueen(int k);
bool valid(int lev);
int main() {
cin >> n;
nqueen(0);
cout << total;
}
bool valid(int lev) {
for (int i = 0; i < lev; i++) {
if ((col[i] == col[lev]) || (abs(col[lev] - col[i]) == lev - i)) {
return false;
}
}
return true;
}
void nqueen(int k) {
if (k == n) {
total++;
} else {
for (int i = 0; i < n; i++) {
col[k] = i; // placing queen
if (valid(k)) nqueen(k + 1); // next row
}
}
}어렵다
알! 고리즘은 너무 어려워
