그래프 탐색 알고리즘 (2) 백트래킹을 중심으로

1. 들어가기

   지난 글에서는, 그래프에 표시된 모든 노드를 탐색하는 방법으로 시작점을 기준으로 가장 먼 곳을 탐색하는 방법인 DFS를  살펴봤다. 필자는 이번 글에서 DFS를 베이스로 하여, N-Queen 문제를 통해 백트래킹을 적용하는 방식을 살펴볼 것이다. DFS로 완전탐색을 하지만, 백트래킹을 통해 탐색의 필요 여부를 따져볼 수 있다. 탐색의 필요 여부는 다음 예에서 확인해 볼 경우로 계산만 해봐도 뚜렷하게 알 수 있다. 5X5 체스판에 퀸이 놓일 수 있는 경우를 계산한다면, 모든 경우의 수는 5^5 가지가 되는데, 백트래킹으로 조건을 둔다면, 필요하지 않은 경우에 대해서는 더 따져볼 필요가 없게 된다. 그래서 경우의 수가 위의 값 보다는 확연하게 줄어들게 된다. 이와 관련해서 더 자세하게 살펴보도록 하자.
 

2. 백트래킹

5 X 5 체스판이 다음과 같이 있다고 하자. 체스판에는 퀸이 5개가 놓일 수 있다. 그런데 이때 퀸이 놓일 수 있는 위치는 서로 인접하지 않은 조건에서만 놓일 수 있다. 예를들어 같은 행에 놓이거나 같은 열에 놓일 수 없고, 같은 대각선에도 놓일 수 없다. 이를 고려하여 퀸이 놓일 수 있는 경우의 수는 5X5 체스판에서 몇 가지에 해당하는 지를 로직을 통해 알아볼 것이다.

5X5 체스판

퀸이 다음과 같이 놓일 수 있는 경우가 있다. 

퀸이 놓이는 경우를 (행, 열) 순의 좌표로 말하면, 다음과 같이 설명할 수 있다.
(1) 퀸이 (0, 0)에 놓여있다고 하자.
     (0, 0) 
(2) 0번 행에 놓인 퀸과 인접한 경우인 같은 줄에 존재하거나 대각선에 존재하는 경우를 제외하면 1번 행에는 퀸이 (1, 2)에 위치한다. 그러므로 2, 3, 4에 대해서는 더 살펴볼 필요가 없으므로 행을 하나 증가시킨다.
     (0, 0) -> (1, 2)
(3) 0번과 1번 행에 놓인 퀸과 인접한 경우인 같은 줄에 존재하거나 0번 행에 놓인 퀸과 1번 행에 놓인 퀸의 대각선에 존재하는 경우를 제외하면 2번 행에는 퀸이 (2, 4)에 위치한다. 그러므로 3, 4에 대해서는 더 살펴볼 필요가 없으므로 행을 하나 증가시킨다.
     (0, 0) -> (1, 2) -> (2, 4)
(4) 0번, 1번, 2번 행에 놓인 퀸과 인접한 경우인 같은 줄에 존재하거나 대각선에 존재하는 경우를 제외하면 3번 행에는 퀸이 (3, 1)에 위치한다. 그러므로 4열에 대해서는 더 살펴볼 필요가 없으므로 행을 하나 증가시킨다.
    (0, 0) -> (1, 2) -> (2, 4) -> (3, 1)
(5) 0번, 1번, 2번, 3번 행에 놓인 퀸과 인접한 경우인 같은 줄에 존재하거나 대각선에 존재하는 경우를 제외하면 4번 행에는 퀸이 (4, 3)에 위치한다. 그러므로 4번 열에 대해서는 더 살펴볼 필요가 없고, 퀸이 5개 존재하므로 탐색을 종료한다.
    (0, 0) -> (1, 2) -> (2, 4) -> (3, 1) -> (4, 3)
위 과정을 따르면, 매 행마다 퀸이 놓일 때, 이전 퀸의 인접성을 따져서 다음 퀸이 놓이는 경우를 볼 수 있다. 이는 백트래킹에 해당한다. 조건을 통해 더 탐색이 필요한지를 따져보게된다. 이를 통해 불필요한 탐색 횟수를 줄일 수 있다.  
 

3. 정리

N-Queen에서의 백트래킹 로직은 다음과 같다
1) 0번 행에서의 퀸의 위치를 가정한다.
2) 0번 행에서의 퀸의 위치와 인접한 위치인 같은 열에 존재하는지, 같은 대각선의 위치에 존재하는 지를 판단한다.
3) 2)를 판단하고 위치가 결정되면 행의 값을 1 증가시킨다
4) 2)와 3)을 반복한다.
5) Queen의 수가 N값과 일치하면 하나의 경우를 찾은 것이므로, 결과로 사용할 변수에 1값을 더해서 할당한다.
 

4. 구현

public class NQueen {
    static int n;
    static int[] board;
    static int cnt;

    static void nQueen(int row) {
        int queen = 0;
        if(row == n){
            cnt++;
            return;
        }

        for(int i=0; i<n; i++){
            queen = 1;
            board[row] = i;
            for (int j = 0; j <row; j++) { //유망함을 판단하는 반복문
                if(board[j] == i || Math.abs(row-j) == Math.abs(i-board[j])){ //Math.abs(row-j) == Math.abs(i-board[j]) 동일한 대각선 위치
                    queen = 0; // j번째 열은 유망하지 않으므로 queen 위치 변수 값을 0으로 할당
                    break;	   // 더 확인할 필요가 없으므로 반복문을 탈출함
                }
            }
            if(queen > 0){ // 유망함이 확인됐다면, row 값을 증가시킴 이때 boolean을 사용해도 무방함
                nQueen(row+1);
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        board = new int[n];

        cnt=0;
        nQueen(0);
        System.out.println(cnt);
    }
}

 

5. N-Queen 에서 백트래킹 구현 시 고려해야 할 사항

- 유망함을 판단하는 조건문 설정
조건문을 설정할 시 같은 열에 위치하는지를 확인하는 조건문을 설정할 때는 어려움이 없다. 그러나 같은 대각선에 위치하는 지를 판단할 때는 이보다 조금 어려울 수 있다. 열의 차이와 행의 차이가 같은 경우는 동일한 대각선에 위치하는 경우이다. 같은 대각선에 위치하는 경우를 조건문으로 어떻게 나타내는지를 숙지해두도록 하자.
 

참고문헌
- 여덟 퀸 문제 : https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C