BOJ - 9663 N-Queen 해결 전략 (C++)

• 문제

  N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

• 입력

  첫째 줄에 N이 주어진다. (1 ≤ N < 15)

• 출력

  첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

• 예제 입력 1
  8
• 예제 출력 1
  92

해결 전략

  가장 기초적인 Backtracking(Backtracing) 연습 문제라고 볼 수 있다. 기본적으로 백트래킹은 State Space Tree에 대한 DFS적인 탐색이다. 따라서 DFS에 대한 이해가 충분하다면, 기본적인 백트래킹 기법 적용은 어렵지 않다.

  하지만, 문제 상황에 따라 상태 트리가 방대할 경우, 백트래킹의 소요 시간이 끝없이 길어질 수가 있다. 따라서 백트래킹 문제 상황에서 가장 중요한 능력은 보다 더 효율적인 탐색을 위한 효율적인 Check함수의 구현, 즉, Pruning이 가장 중요하다. Naive한 DFS식 탐색 형태에서 몇 가지 Pruning 기법을 적용해 보다 더 빠른 탐색을 도모하는 것이 중요한 것이다.

  본 문제는, 시간 제한 조건과 문제 상황을 통해 백트래킹 문제임을 어렵지 않게 예측할 수 있는 유형이다. 결국 핵심은 효율적인 탐색을 위해 어떠한 Check 방식을 둘 것인지가 중요하다. (배경 지식 : 퀸은 상하좌우, 대각선 방향으로 기물이 없는 칸에 한해서 칸수의 제한 없이 움직일 수 있다.)

  본인은 몇 차례의 고민 후 다음과 같은 백트래킹 탐색 알고리즘과 Pruning을 적용했다.

1. 우선, 2차원 배열 형태의 보드판을 기본적으로 DFS 탐색을 한다.

2. 이때, updateBoard라는 함수를 도입하는데, 이는, [x][y] 위치에 퀸이 놓이면, 그 퀸의 공격 가능 위치들에 표시를 해주는 함수이다. (공격 가능 해제 시에도 사용)

3. 이때, 이러한 updateBoard 함수는 board라는 2차원 배열에 +1, -1을 함으로써 작동하는데, 이는 중첩적인 공격 가능 상황을 인식하기 위함이며, 이말은 즉슨, board의 요소값이 0인 경우를 제외하고는 항상 공격 대상 위치임을 의미한다.

4. 3번의 논리에 의해, DFS 탐색 시 board가 0인 위치만 탐색하도록 한다.

5. 하지만, 4번까지의 알고리즘은 부족하다. 한 가지 더 Pruning 기법이 필요하다. (여기까지는 N이 12이상일 경우 시간 초과가 난다.)

   체스판에 N개의 퀸이 놓일 수 있는 가능 조합을 확인해보면, 결국, 한 라인에 반드시 딱 하나의 퀸이 존재해야한다.

6. 5번 이유에 의해, DFS 탐색에서 굳이 2차원 중첩 반복을 할 필요 없이, 하나의 라인에 대해서만 탐색을 수행하면 된다.

  이러한 원리로 본 문제를 해결할 수 있다. 효율적인 Pruning을 위해 문제에 숨겨진 원리를 찾아내는 능력이 중요함을 느낄 수 있는 문제라 할 수 있다.

  아래는 코드이다.

#include <iostream>
#include <algorithm>
// BOJ - 9663 N-Queen
using namespace std;

int board[15][15];
int cnt, waycnt;

void updateBoard(int n, int x, int y, int option) {
	for (int i = 0; i < n; i++) {
		board[i][y] += option; board[x][i] += option;
	}

	int i = x, j = y;
	while (i >= 0 && j >= 0 && i < n && j < n) board[i++][j++] += option;
	i = x, j = y;
	while (i >= 0 && j >= 0 && i < n && j < n) board[i--][j++] += option;
	i = x, j = y;
	while (i >= 0 && j >= 0 && i < n && j < n) board[i++][j--] += option;
	i = x, j = y;
	while (i >= 0 && j >= 0 && i < n && j < n) board[i--][j--] += option;
	board[x][y] -= 5 * option;
}

void solve(int n, int x, int y) {
	if (cnt == n) { waycnt++; return; }

	for (int j = 0; j < n; j++) {
		if (board[x][j] == 0) {
			updateBoard(n, x, j, 1); cnt++;
			solve(n, x + 1, j);
			updateBoard(n, x, j, -1); cnt--;
		}
	}

	return;
}

int main(void) {
	int n;

	cin >> n;
	solve(n, 0, 0);
	cout << waycnt;
		
	return 0;
}