크기가 인 체스판위에 개의 Queen 을 서로 잡지 못하게 배치할 때 최대 몇 가지 경우의 수가 있는지 구하시오. 체스에서 Queen은 대각선과 상하좌우 총 8방향으로 거리 제한 없이 한번에 움직일 수 있는 기물이다.
단순하게 완전 탐색의 개념으로 접근하면 개의 기물을 개의 칸에 높는 방법의 수가 되므로 경우의 수는 이 된다. 이는 이 10일 때 라는 어마어마한 경우의 수가 나온다. 따라서 단순한 완전 탐색으로는 이 문제를 시간 내에 해결할 수 없다. 문제를 다시 읽어보면 모든 퀸은 서로 잡을 수 없어야 하므로 각 행, 열, 대각선에 1개 이상의 퀸을 배치할 수 없다. 즉, 어떤 칸에 퀸을 배치했다면 그 칸과 같은 행/열/대각선에는 다시 퀸을 배치할 필요가 없다. 이러한 제약 조건들을 고려하면 계산량을 획기적으로 줄일 수 있다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> arr; // 이전 퀸 배치 저장 ( arr[x] = x행의 arr[x] 열에 퀸이 있음 )
int n, tot = 0;
void r(int x) {
if(x == n + 1) { // 각 행마다 1개의 퀸을 배치했으므로 마지막 행까지 코드가 진행되었다면 N개의 퀸 배치에 성공한 것이다.
tot++;
return;
}
for(int i=1;i<=n;i++) {
int sign = 0;
for(int j=1;j<x;j++) { // 이전 배치된 퀸과 겹치는지 확인
if(i == arr[j] /*같은 열인지 확인*/ || abs(i - arr[j]) == abs(j - x) /*같은 대각선인지 확인*/) { // 이전 퀸과 겹치는 경우
sign = 1;
break;
}
}
if(sign == 0) {
arr[x] = i; // 현재 위치에 퀸 배치
r(x + 1); // 다음 행 탐색
}
}
}
int main() {
cin >> n; arr = vector<int>(n + 1);
r(1); // 1행부터 퀸 배치 시작
cout << tot;
return 0;
}