N queen

난 컴공이라고 하기엔 애매한 학부를 졸업했다. 해서 알고리즘등과 같은 전산학 이론에 다소 취약하다.

그래도 꾸준하게 공부하고 정리해가다 보면 빠삭해지지 않을까.

어찌되었건 오늘은 N queen을 공부해보았다. 사실 이전에 풀은 기억이 있고 그때 풀었던 코드를 다시 봤는데

내가 풀었는데 이해가 안간다. 그래서 다시 차근차근 살펴보았다.

N queen. 알고리즘의 Backtracking을 다룰때 매우 빈번하게 등장하는 아무 유명한 문제이다. 문제는 간단하다. 

---

문제

"N*N의 Table에서 체스unit Queen N개가 서로 공격하지 않게 놓일 수 있는 경우의 수"

 

예를 들어 N=4일때, 4개의 Queen이 놓일 수 있는 경우는 아래와 같다.

---

주요 아이디어

1. 퀸의 특성상, 한 행에 하나의 퀸만 있을 수 있다.

2. 퀸들은 같은 행, 열, 대각선에 있을 수 없다.

3. 전수조사를 하되 유망하지 않은 노드는 탐색하지 않는다.

4. 일차원배열을 사용하되 행과 열을 표현한다.

    - 해당 내용이 잘 이해가 안갈 수 있는데 그림으로 표현하면 아래와 같다. 배열의 각 자리는 '행'을 나타내며 각 자리의 값은 '열' 나타내는 것이다. 

퀸의 자리를 나타내는 배열, (0,2), (1,3)을 나타낸다.

 

여기서 적용되는 개념이 백트래킹(Backtracking)이다.

백트래킹(Backtracking)

백트래킹은 전수 조사를 기본으로 한다. 즉, 모든 경우의 수를 본다는 것이다. 실제 구현시에는 깊이 우선 탐색(DFS)으로 구현될 수 있다. 그러나 모든 경우의 수를 수행하기 위해서는 매우 비효율적이며 알고리즘의 시간복잡도가 증가한다. 따라서 백트래킹에는 아래 2가지 기법이 적용된다.

Promising : 방문 노드에 대하여 해를 구하기 위한 조건에 부합한지 검사

Pruning : Promising을 통해 조건에 부합하지 않다면 해당 노드를 포함한 하위 노드는 방문하지 않음, 일명 가지치기

 

2가지 방법을 통해 탐색시간을 줄일 수 있다. N queen은 해당 개념을 적용하여 풀이가 된다.

N queen의 Promising : 현재 판단 중인 노드와 같은 행, 열, 대각선에 Queen이 배치되어 있는지 검사

N queen의 Pruning : 배치되어 있다면 해당 노드는 방문하지 않음

 

즉, 각 노드를 방문하며 전수 조사를 기본으로 하되 같은 행, 열, 대각선에 Queen이 있다면 방문하지 않는 것이다.

 

위의 과정을 거쳐 탐색을 끝마쳤다면 N개의 Queen이 배치되었을 것이다.

---

코드

 

InputData() : N을 사용자로 부터 입력받는다.

Promising(int row) : 판단하려는 row를 전달받고 이전의 행들과 판단하는 행을 비교한다. 같은 열, 대각선

                          같은 열? col[row]와 col[i]들을 비교한다.

                          대각선? (a,b), (c,d) 두점이 있을시 절대값(a-c) == 절대값(b-d)는 대각선에 위치한다.

Dfs(int row) : 전달 받은 row가 N과 같으면 해를 구한 것이다. N-1까지 Queen을 놓았기 때문에. 재귀 종료조건.

                  전달 받은 row를 기준으로 col마다 Promising을 하여 유효하면 다음행(row+1) 재귀함수를 호출한다.

#include <stdio.h>
#include <stdlib.h>
 
#define MAXN (12)
 
int N;
int col[MAXN];
int ans = 0;
 
void InputData(void){
    scanf("%d", &N);
}
 
int Promising(int row){
    int rtnV = 1;
    for(int i=0; i<row; i++){ //현재 판단중인 row 이전까지만 비교
        if(col[row]== col[i]) rtnV = 0; // 같은 열에 있는지 비교
        if(abs(row-i) == abs(col[row]-col[i])) rtnV = 0; // 대각선에 있는지 비교
    }
    return rtnV;
}
 
void Dfs(int row){
    if(row == N){ //Node를 N-1보다 더 넘어왔다. 종료조건
        ans++;
        return;
    }
 
    for(int i=0; i<N; i++){//열
        col[row] = i; //행자리에 열값 입력
        if(Promising(row)){ //Pruning
            Dfs(row+1);
        }
    }
}
 
int main(void)
{
    InputData();
    Dfs(0); //0번 행 출발

    printf("%d\n", ans);
    return 0;
}

 

N queen은 관련개념이나 기법을 숙지하지 않은 채로 접근하면 코드를 보아도 이해가 잘 가지 않는 것 같다. 다만 개념과 포인트를 알고부터는 코드가 눈에 쉽게 들어오게 되는 것 같다. Promising과 Pruning을 잘 기억해두자.