알고리즘 - 백트래킹(Backtracking)

 

1. 백트래킹이란?

 

백트래킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지(유망하지 않은지) 판단하고 그러한 경우 해당 상태(노드)를 제외하고 다음 단계로 나아가는 방식이다.

여기서 알아둘 것은 특정 상태(노드)를 제외한다는 것이다.

 

백트래킹은 현재 상태(노드)에서 다음 상태(노드)로 나아갈 수 있는 모든 경우를 찾되, 그 중 유망하지 않다면 현재에서 더 이상 나아가지 않고 이전의 상태(노드)로 돌아가 다음 상태(노드)를 검사한다.

여기서 더 이상 탐색할 필요가 없는(유망하지 않은) 상태(노드)를 제외하는 것을 가지치기(pruning)라고도 한다.

즉, 이 방법을 통해 우리는 모든 경우의 수를 체크 하지 않고 필요한 것만 체크하여 전체 풀이 시간을 단축할 수 있게 된다!

 

백트래킹을 사용하는 알고리즘 중 하나는 대표적으로 DFS가 있다. (관련 포스팅은 여기) DFS는 재귀를 통해 가능한 경로 중 유망한 경로만 찾아서 탐색을 수행한 뒤 다시 돌아와 그 중 가장 최적의 경로를 반환한다.

 

백트래킹을 사용해 해결할 수 있는 문제는 의사 결정, 최적화, 열거하기 등의 경우가 있다.

사실 백트래킹은 사용 가능한 경우가 많지만 시간복잡도가 보통 Exponential(지수, $2^n$ 꼴)이며, 대부분 Dynamic Programming, 그리디 알고리즘 등으로 더 빠르게 해결할 수 있다.

하지만 일부 경우의 문제들은 여전히 백트래킹으로만 해결이 가능한 문제도 있으며 그러한 경우에 많이 사용된다.

 

 

2. 백트래킹 사용 예

 

N-Queen 문제를 통해 한 번 사용을 어떻게 하는지, 백트래킹이 어떤 것인지 이해해보자.

N-Queen 문제는 N 개의 체스 퀸을 NxN 크기의 체스보드에서 움직이되 상호 공격을 하지 않도록 움직이는 방법이다. 아래와 같이 배치하게 되면 정답이다.

 

 

이를 정답으로 표시한다면, 4x4의 배열에 퀸의 위치는 1로, 나머지는 0으로 표시한다면 정답이 될 것이다.

 

어떻게 해결할 수 있을까?

1) 우선, 제일 좌측 열에서 시작하여 하나씩 비교하여 해당 열의 모든 행에 퀸이 이미 배치되었는지 체크한다.

 

 

 

2) 각 행을 체크 시, 퀸이 없다면 우선 유망한 후보로 고르고, 해당 행 전체를 조사하여 퀸이 배치되었는지 조사한다. 예를 들어 0x0의 위치를 유망하다고 본다면 아래와 같이 체크한다.

 

 

 

3) 행 또한 체크를 완료했다면, 대각선으로 체크하여 퀸이 배치된 내역이 있는지 확인한다. 아래 그림과 같다.

 

4) 이를 통해 모두 비어 있다면 해당 위치에 퀸을 놓고 다음 열에서도 동일하게 체크를 수행한다. 이를 통해 3번째 열까지 체크하면 다음과 같이 퀸이 배치될 것이다.

▶ 위에서와 같이, 3번째 열에서는 어떠한 곳에도 퀸을 배치할 수 없다! 그러니 백트래킹을 통해 2번째 열로 돌아가 다시 다른 행에 배치하게 된다.

 

5) 위 과정을 반복하여 전체 퀸을 모든 열에 놓을 수 있는 경우를 찾을 때까지 반복한다.(재귀 + 반복문 기반 백트래킹 사용)

위의 예시는 아래와 같이 결국 정답을 아래와 같이 얻을 수 있다.

 

 

 

3. N-Queen 문제 코드로 구현하기

 

이번엔 위의 경우를 N-Queen으로 한 번 코드 구현해보자.

public class NQueen{
    static int N = 4;
    static int[][] board = new int[4][4];
    public static void main(String[] args){
        if(put_queen(0) == false){
            System.out.println("Solution does not exist!");
        } else {
            for(int i=0; i < N; i++){
                for(int j=0; j < N; j++){
                    System.out.print(board[i][j] + ", ");
                }
                System.out.println();
            }
        }
    }
    
    // 재귀와 반복을 통해 문제를 해결하는 메소드(각 컬럼에 대해 체크)
    private static boolean put_queen(int col){
        // N보다 열의 숫자가 높거나 같다면 모든 열에 퀸이 배치된 상태를 의미
        if(col >= N) return true;
        
        // 현재 열(Column)에서 각 행을 하나씩 체크한다.
        for(int i=0; i < N; i++){
            // 현재 열의 i번째 행에 퀸을 위치시킬 수 있는지 파악
            if(check(i, col) == true){
                board[i][col] = 1;
                
                // 위치 시켰으면, 이후 열에 대해서도 연속적으로 가능한지 확인!
                if(put_queen(col+1) == true){
                    return true;
                }
                
                // 만약 이후 열에 대해서 true 반환이 안되었다면 다시 0으로 수행하고
                // 백트래킹을 통해 다음 row로 넘어가서 수행
                board[i][col] = 0;
            }
        }
        // true를 이전에 반환 못했다면 답이 없는 것이므로 false 반환
        return false;
    }
    
    // 현재 행/열에 퀸이 이미 배치된 상태인지 확인하는 메소드
    private static boolean check(int row, int col){
        int i,j;
        
        // 현재 행의 모든 열에 퀸이 있는지 테스트
        for(i = 0; i < col; i++){
            if(board[row][i] == 1){
                return false;
            }
        }
        
        // 현재 위치의 좌상단 대각선으로 퀸이 있는지 테스트
        for(i = row, j = col; i >= 0 && j >= 0; i--, j--){
            if(board[i][j] == 1){
                return false;
            }
        }
        
        // 현재 위치의 우하단 대각선으로 퀸이 있는지 테스트
        for(i = row, j = col; i < N && j >= 0; i++, j--){
            if(board[i][j] == 1){
                return false;
            }
        }
        return true;
    }
}

 

※ 참고 - 다른 백트래킹 문제!
1. The knight's tour problem(참고)
2. Rat in a Maze(참고)
3. Subset Sum(참고)
4. m Coloring Problem(참고)

관련 문제들의 링크 또한 옆에 있으니 참고하면 좋은 공부가 될 수 있습니다.

 

참고) DFS와 백트래킹(Backtracking)의 차이


DFS는 기본적으로 그래프 형태 자료구조에서 모든 정점을 탐색할 수 있는 알고리즘 중 하나이다. 깊이를 우선적으로 탐색하기에 재귀 또는 스택을 이용한다.


재귀를 이용하여 탐색을 수행한다는 부분에서 완전탐색 알고리즘의 재귀 / 백트래킹(Backtracking)과 유사한 측면이 보여 혼란이 올 수 있다.


그런데, 재귀라는 것은 말 그대로 스스로의 함수(또는 메소드)를 호출하는 방식을 의미하는 것이므로 DFS가 재귀라는 방식을 이용해 탐색을 수행하는 것으로 하나의 방식이라고 이해하면 된다.


또한 백트래킹(Backtracking)은 재귀를 통해 알고리즘을 풀어 가는 기법 중 하나로 가지치기(Pruning)을 통해서 탐색을 시도하다가 유망하지 않으면 추가 탐색을 하지 않고 다른 해를 찾는 방법이다.


DFS는 기본적으로 모든 노드를 탐색하는 것이 목적이지만 상황에 따라서 백트래킹 기법을 혼용하여 불 필요한 탐색을 그만두는 것이 가능하다.




즉, DFS와 백트래킹은 유사한 부분이 있으며 기본적으로 사용 목적이 다르지만 두 기법을 혼용하여 사용하는 것이 가능하다. 완전히 다른 개념이 아니라 재귀 호출을 통한 기법 중 하나 이기 때문이다.

 

긴 글 읽어주셔서 감사합니다.