[백준] 9663 N-Queen

 

 

알고리즘 문제 중에서는 매우 유명한 N-Queen 문제다. 문제는 다음과 같다.

 

크기가 NxN인 체스판에 N개의 퀸을 둔다. 퀸은 서로 공격할 수 없는 상태여야 한다. 이때, 퀸을 배치할 수 있는 경우의 수를 출력하시오.

---

이 문제는 백트래킹을 이용하여 풀 수 있는 문제이다. 백트래킹 알고리즘은 초보자에겐 어려울 수 있으나, 필수적으로 알아야 할 알고리즘이다.

 

백트래킹 알고리즘을 간단히 정리하면 "가능성이 없는 경우에 대해선 탐색을 하지 않는다" 이다. 즉, 모든 경우에 대하여 탐색을 하지 않고 가능성이 있는 경우에 대해서만 탐색을 하여 답을 찾는것이 이 문제의 목표이다.

 

이러한 생각으로 문제를 다시 풀어보자. 나는 체스를 모르기 때문에, 퀸이 공격할 수 있는 경우부터 알아보자. 퀸은 가로 세로 대각선 모든 직선으로 공격이 가능하다.

 

 

위 사진을 보면 '퀸' 옆에 빨간색 화살표가 있다. 빨간색 화살표 경로에는 퀸이 올수가 없다. 공격이 가능하기 때문이다. 즉, 이 문제는 가로 세로 대각선 방향으로 퀸이 보이면 안 된다는 것이다. 아래 사진은 N=4일 경우에 답이 되는 경우 중 하나이다.

 

 

목표를 알았으니, 백트래킹에 대해서도 알아보자. 앞서 말했듯이, 백트래킹은 "가능성이 있는 경우만 탐색" 하는 알고리즘이다. 4x4 체스판에 대해서 예를 들어보자. 위에 있는 체스판이 존재한다고 가정하자. 실제 계산은 그림의 아래에 있는 1차원 배열에 값을 넣으면서 진행할 것이다.

 

탐색 진행

---

먼저 (0,0)에 퀸을 배치한다.

 

 

다음에는 (0,1)에 퀸을 배치한다. 여기서 앞에서 배치했던 퀸을 공격할 수 있다. 그러면 이 경우는 넘기고 다음 (1,1)에 퀸을 배치한다.

 

 

이 경우도 대각선으로 충돌한다. 다음으로 넘어가자.

 

 

이 경우에서는 어떠한 충돌도 일어나지 않는다. 이렇게 배치했을 때 정답이 나올 수도 있다. (라고 가정한다. 하지만 실제로는 (0,0)에 퀸을 배치해서는 안된다.)

 

 

다음 칸으로 넘어가서 (0,2)에 퀸을 배치한다. 하지만 (0,0) 퀸을 공격할 수 있으므로, 다음 경우로 넘어간다. 

이 과정을 반복했을 때 처음으로 나오는 배치 가능한 경우는 아래 사진과 같다.

 

 

이러한 경우가 나왔을 때, count를 1씩 올려준다. 

위와 같은 탐색의 공통점은 "유망하지 않은 경우의 수는 내친다" 라는 것이다. 이러한 구조는 재귀 함수로 구현이 가능하며, 코드의 구조를 알아두면 매우 편하다.

 

#include <iostream>
#include <cstring>
using namespace std;
 
#define BOARD_MAX 15
 
int arr[BOARD_MAX];
int sum, n;
 
/* 배치된 퀸이 조건에 맞는지 판별하는 함수 */
int correct(int index)
{
    int check, i = -1;
 
    while (++i < index)
    {
        check = arr[i] - arr[index];
        if (check < 0)
            check *= -1;
        if (arr[index] == arr[i] || check == index - i)
            return (0);
    }
    return (1);
}
 
/* 재귀함수가 돌아가면서 백트래킹을 실행한다. */
void rec(int start)
{
    int i = -1;
 
    /* 체스판에 퀸이 N개 채워졌을 경우 */
    if (start == n)
    {
        sum++;
        return;
    }
    while (++i < n)
    {
        arr[start] = i;
        if (correct(start))
            rec(start + 1);
    }
}
 
/* 배열 초기화 후 백트래킹 실행 */
void ten_queens_puzzle(void)
{
    int i = -1;
 
    sum = 0;
    memset(arr, 0, sizeof(arr));
    rec(0);
}
 
int main()
{
    cin >> n;
    ten_queens_puzzle();
    cout << sum;
}

 

백트래킹 기법을 활용하면 유망하지 않는 중간의 경우를 제거함으로서, 탐색하는 경우의 수를 줄여줄 수 있다는 장점이 있는 알고리즘이다.