백트래킹 (Back Tracking)

1. 백트래킹이란?

답을 찾는 도중 답이 아니어서 막히게 되면, 되돌아가서 다시 답을 찾아가는 기법.

최적화 문제와 결정 문제를 푸는 방법이 된다.

 

2. DFS와 차이점

깊이 우선 탐색의 경우 가능한 모든 경로를 탐색한다.

따라서 불필요한 경로들도 다 탐색하게 되어, 경우의 수를 줄이지 못한다.

결국 N! 가지의 경우의 수를 가진 문제는 깊이 우선 탐색으로 처리가 불가능하다.

 

백트래킹의 경우 지금의 경로가 답이 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다.

반복문의 횟수를 줄일 수 있으므로 효율적이다.

이를 가지치기(Pruning)라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다.

N! 가지의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다.

가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

 

3. 예제

[ N-Queen 문제 ]

크기가 N * N인 체스판 위에 퀸  N개를 서로 공격할 수 없도록 놓는 경우의 수를 구하시오.

퀸을 놓았을 때 퀸 자신을 기준으로 일직선상(가로 및 세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다.

 

4. 코드

public class BackTracking {
    static int n, result = 0;
    static int[] board;

    public static void main(String[] args){
        n = 4;
        board = new int[n];

        solution(0);
        System.out.println(result);
    }

    //퀸은 각  행과 열에서 오직 하나만 존재할 수 있기 때문에, 이차원 배열을 일차원 배열로 압출할 수 있다.
    //일차원 배열로 구현시 행은 행, 값은 열을 의미
    public static void solution(int row){
        if(n == row){
            result++;
            return;
        }

        for (int column = 0; column < n; column++){
            board[row] = column;

            if(promising(row)){
                solution(row + 1);
            }
        }
    }

    static boolean promising(int row){
        for (int older = 0; older < row; older++){
            //같은 열인지 체크 || 대각선 체크
            if(board[row] == board[older] || Math.abs(row - older) == Math.abs(board[row] - board[older])) return false;
        }

        return true;
    }
}