백트래킹은 "가능한 모든 경우의 수를 탐색하되, 불필요한 경우는 조기에 제외하여 탐색 범위를 줄이는 기법"입니다. 일반적으로 재귀 함수를 이용하여 구현됩니다. 재귀 호출을 하면서 각 단계에서 선택 가능한 모든 옵션을 시도하고, 조건에 맞지 않는 옵션은 배제하여 다음 단계로 진행합니다.

백트래킹의 특징

• 모든 가능한 경우의 수를 탐색하기 때문에 완전 탐색에 속합니다.
• 일반적으로 완전 탐색은 지수 시간 복잡도를 가지므로, 입력 크기가 큰 경우에는 비효율적일 수 있습니다.
• 하지만, 백트래킹은 불필요한 경우의 수를 제거하여 탐색 범위를 줄이기 때문에 상황에 따라 효율적인 경우가 있습니다.

백트래킹의 장단점

장점

• 모든 가능한 경우를 고려하기 때문에 정확한 해를 찾을 수 있습니다.
• 조건에 맞지 않는 경우를 배제하여 탐색 시간을 단축할 수 있습니다.

단점

• 입력 크기가 큰 경우에는 탐색 시간이 길어질 수 있습니다.
• 최적해가 아닌 근사해를 찾는 경우가 있을 수 있습니다.

구현 방법 및 Java 코드 예제

• N-Queen문제
  • N X N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수

// 알고리즘 - 백트래킹

public class Main {

    static int n = 4;
    static int[] board = new int[n];
    static int cnt;

    public static int nQueen(int row) {
        if(row == n){
            cnt++;
            for (int i = 0; i < n; i++) {
                System.out.print(board[i] + " ");
            }
            System.out.println();
            return cnt;
        }
        
        for (int i = 0; i < n; i++) {
            board[row] = i;

            // promising
            if(isPromising(row)){
                nQueen(row + 1);
            }
        }

        return cnt;
    }

    public static boolean isPromising(int row){
        for (int i = 0; i < row; i++) {
            if(board[row] == board[i] || row - i == Math.abs(board[row] - board[i])){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("경우의 수: " + nQueen(0));  // 2
    }
}