문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 이 주어진다.
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
풀이
한 행에 퀸을 하나씩 놓는다고 정하면, 같은 행 충돌은 애초에 생기지 않는다. 따라서 이전 행들에 놓인 퀸과 같은 열인지, 또는 같은 대각선인지 확인하면서 가능한 열만 시도하면 된다.
코드는 visit[row]에 해당 행의 퀸 열 위치를 저장한다. 새 퀸을 놓을 때는 앞선 행들을 훑으며 열이 같은지, 행 차이와 열 차이가 같아 대각선에 놓이는지 검사한다. 불가능한 위치를 바로 건너뛰는 백트래킹이 핵심이다.
코드
#include <iostream>
using namespace std;
const int MAXN = 16;
int visit[MAXN];
int n, ans = 0;
bool check(int row, int col) {
for (int i = 0; i < row; i++) {
//1. 같은 열에 퀸이 존재하는지 판별
//2. 대각선에 퀸이 존재하는지 판별
//nQueen 함수에서 각 행마다 퀸을 배치하기 때문에 이곳에서 판별할 필요 없음
if (col == visit[i] ||
abs(col - visit[i]) == abs(row - i))
return false;
}
return true;
}
void nQueen(int curRow) {
if (curRow == n) {
//curRow와 n이 같아졌다면 모든 퀸의 배치가 끝난 경우
//ans를 1 증가시키고 해당 경우 종료
ans++;
return;
}
for (int i = 0; i < n; i++) {
if (check(curRow, i)) {
//둘 수 있는 퀸의 위치인 경우
//현재 퀸의 위치 : (curRow, i)
visit[curRow] = i;
nQueen(curRow + 1);
}
}
}
void solve() {
cin >> n;
nQueen(0);
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도: 가능한 퀸 배치를 백트래킹으로 탐색하므로 최악의 경우 이다.
- 공간 복잡도: 행별 퀸 위치 배열과 재귀 스택을 사용하므로 이다.
마무리
행을 하나씩 채우며 열과 대각선 충돌만 검사하면 탐색 공간을 크게 줄일 수 있다. N-Queen은 가능한 위치를 놓고 되돌리는 백트래킹의 전형적인 문제다.
