N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
#include <iostream>
using namespace std;
/* 조건 */
#define MAX 15
/* 변수 */
int N, ans = 0;
bool board[MAX][MAX]; // queen이 존재할 경우 true
/* 함수 */
bool isAvailable(int x, int y) {
// 가로 세로 확인
for(int i = 0; i < N; i++) {
if(board[x][i] == true) return false; // x축으로 움직이므로 사실 필요 X
if(board[i][y] == true) return false;
}
// 대각선 확인
for(int i = 0, j; i < N; i++) {
j = y - x + i;
if(j >= 0 && j < N && board[i][j] == true) return false;
j = y + x - i;
if(j >= 0 && j < N && board[i][j] == true) return false;
}
return true;
}
void putQueen(int x, int y, int count) { // (x, y)에 넣음. count는 놓인 횟수
if(isAvailable(x, y)) { // 놓을 수 있는 경우
if(count == N) { // 모두 놓은 경우
ans++;
return;
}
board[x][y] = true; // queen을 놓고
for(int i = 0; i < N; i++) // x + 1줄에 놓아봄
putQueen(x+1, i, count+1);
board[x][y] = false;
} else return;
}
int main() {
/* Fast cin cout */
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
/*****************/
/* 입력 */
cin >> N;
for(int i = 0; i < MAX; i++) {
for(int j = 0; j < MAX; j++) {
board[i][j] = false;
}
}
/* 풀이 */
for(int i = 0; i < N; i ++) {
putQueen(0, i, 1); // x = (0, i)에 '1번째'로 넣음
}
/* 출력 */
cout << ans << '\n';
}
board[x][y]는 (x, y)좌표에 queen을 놓았으면 true를, 빈 칸은 false를 저장하는 배열이다.
위 배열에 board[0][0]부터 board[N-1][0]까지 하나를 놓는 것으로 시작해 다음 줄에 하나씩 놓아보면서 가능한 경우를 탐색한다.
사용한 알고리즘(?)은 백트래킹 기법으로, N개를 놓을 때 까지 탐색한다.