[알고리즘] 백트래킹(Backtracking) | C언어 N-Queen구현

백트래킹이란?

• 백트래킹(Backtracking) 은 해를 찾는 도중 해가 아니어서 막힌다면, 되돌아가서 다시 해를 찾아가는 기법이다.
• 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더이상 가지 않고 되돌아간다. 이것을 가지치기(Pruning) 이라고 한다.
• 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것이다. 
• 해가 될 가능성이 있다면 유망하다(promising)고 한다.

 

N-Queen 문제

N-Queen 문제는 N X N 크기의 체스판에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 문제이다. 이 때 퀸은 상하좌우, 대각선 방향으로 체스판의 끝까지 공격을 할 수 있다. 따라서 아래 그림처럼 직선, 대각선 상에는 퀸을 배치 할 수 없다.

N-Queen 문제는 N의 크기가 작다면 DFS 방식으로 모든 경우의 수를 탐색하면 답을 찾을 수 있다. 하지만 N의 크기가 커질 수록 탐색해야할 경우의 수가 기하급수적으로 증가한다. 아래 그림을 살펴보자.

상태 공간 트리

위 그림은 4 x 4 퀸 문제에서의 상태 공간 트리(State Space Tree)를 나타낸다. 여기서 상태 공간 트리란 모든 가능한 후보 해결법을 트리로 나타낸 것을 의미한다. 각 노드는 (행의 위치, 열의 위치)를 나타낸다. 예를 들어 (2,3) 은 2행 3열을 의미한다. 위와 같이 모든 경우의 수, 즉 퀸을 모든 위치에 배치해보는 방법은 O(N^N)이 걸린다. 매우 비효율적이다.

 

 

하지만 백트래킹을 이용하여 가지치기를 한다면 어떨까?

제일 먼저 (1,1) 에 퀸을 배치하고, 2행에서 퀸을 어디에 배치할 지 결정한다고 하자. 이 때 (2,1)은 직선상이고 (2,2)는 대각선상이라서 유망하지 않으므로(Not Promising) 해당 노드로 경로를 탐색하지 않는다(Pruning). 이후 (2,3)을 선택한다고 하자.

 

위 그림을 보면 3행에는 아무데도 퀸을 배치할 수 없는 것을 알 수 있다. 따라서 이 경로를 더 이상 탐색하지 않고 다시 2행으로 돌아가 유망한(promising) 노드인 (2,4)를 선택한다. 

 

위 그림을 보면 (3,1) (3,3) (3,4) 에는 퀸을 배치 할 수 없는 것을 알 수 있다. 따라서 이 경로를 더 이상 탐색하지 않고 유망한 노드인 (3,2)를 선택한다.

 

위 그림을 보면 4행에 어디에도 퀸을 배치 할 수 없는 것을 알 수 있다. 이 때 (1,1) 을 선택했을 경우 어떤 경우에도 퀸을 제대로 배치 할 수 없는 것을 확인했으므로 1행으로 돌아가 (1,2)를 선택한 후 다시 탐색을 진행하면 된다.

 

위와 같이 계속해서 유망한 노드 탐색, 가지치기를 진행하며 탐색하면 아래와 같은 결과를 얻을 수 있다.

이렇게 백트래킹을 이용하여 N-Queen 문제를 해결할 경우, 단순 DFS 방식보다 훨씬 효율적으로 답을 찾아 낼 수 있다.

 

 

C언어 구현

C언어로 N-Queen 문제를 구현해보자. 먼저 n*n 크기의 체스판에 어디에 퀸을 둘 지 저장할 배열이 필요하다. 이 때 많이들 2차원 배열을 생각하지만 그럴 필요없이 1차원 배열이면 충분하다. 그 이유가 무엇일까? N-Queen 문제는 무조건 한 행에  하나의 퀸을 배치하게 된다. 따라서 예를 들어 4x4 체스판에서 다음과 같이 퀸의 위치를 나타낼 수 있다.

col[1] = 2 : 1행 2열에 퀸이 있다.
col[2] = 4 : 2행 4열에 퀸이 있다.
col[3] = 1 : 3행 1열에 퀸이 있다.
col[4] = 3 : 4행 3열에 퀸이 있다.

 

 

다음으로 상태공간트리를 어떻게 구현하면 좋을까? 트리를 구현하는 방식도 있겠지만 굳이 그렇게 할 필요 없이 DFS처럼 재귀 방식을 사용하면 된다.

void printQueens()
{
    int i;
    printf(" ");
    for (i = 1; i <= n; i++)
        printf("(%d, %d)\n ", i, col[i]);
    exit(1);
}
 
void queens(int i)
{
    int j;
 
    if (promising(i))    // 유망하다면  
    {
        if (i == n)    // 마지막 행까지 선택이 끝났다면 
        {
            printQueens();    // 퀸의 위치 출력 
            return;
        }
        else    // 아직 끝나지 않았다면 
        {
            for (j = 1; j <= n; j++)    // 모든 열 탐색 
            {
                col[i + 1] = j;
                queens(i + 1);
            }
        }
    } 
 
}

int promising(int i)    // 유망한지 체크 
{
    int k = 1;
    int flag = 1;
    while (k < i)
    {
        if (col[i] == col[k] || abs(col[i] - col[k]) == abs(i - k))    // 상하좌우, 대각선 상에 있는 지 
            flag = 0;
        k++;
    }
    return flag;
}

 

전체 소스코드

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int n;    // n x n 보드판의 크기 n 
int *col;    // 각 행별로 퀸의 열(column) 위치 
 
void printQueens()
{
    int i;
    printf(" ");
    for (i = 1; i <= n; i++)
        printf("(%d, %d)\n ", i, col[i]);
    exit(1);
}
int promising(int i)    // 유망한지 체크 {    int k = 1;    while (k < i)    {        if (col[i] == col[k] || abs(col[i] - col[k]) == abs(i - k))    // 상하좌우, 대각선 상에 있는 지           return 0;        k++;    }    return 1;}
void queens(int i)
{
    int j;
 
    if (promising(i))    // 유망하다면  
    {
        if (i == n)    // 마지막 행까지 선택이 끝났다면 
        {
            printQueens();    // 퀸의 위치 출력 
            return;
        }
        else    // 아직 끝나지 않았다면 
        {
            for (j = 1; j <= n; j++)    // 모든 열 탐색 
            {
                col[i + 1] = j;
                queens(i + 1);
            }
        }
    } 
 
}
 
 
int main()
{
    printf("Input N: ");
    scanf("%d", &n);
    col = (int*)malloc(sizeof(int)*(n+1));
    queens(0);
    printf("No solution");    // 해결법이 없을 경우 
    
    return 0;
}

 

실행결과

 

 

---