Backtracking(백트래킹)

1. 핵심 개념 요약

• 의미: 가능한 해를 모두 고려하되, 조건에 맞지 않으면 되돌아감

• 활용: 완전 탐색보다 효율적이며, 가지치기(pruning)를 통해 시간 단축

• 주요 사용처: 순열, 조합, N-Queen, 미로 탐색, 스도쿠

2. 동작 원리

1. 현재 상태에서 가능한 선택을 하나 고름

2. 그 선택이 유망한지 검사

3. 유망하다면 재귀적으로 다음 선택 진행

4. 조건에 맞지 않으면 되돌아가서(Backtrack) 다른 선택 시도

3. 예제 코드 (Java) - 숫자 1~3으로 만든 길이 2의 순열

public class BacktrackingExample {
    static int N = 2; // 만들 조합의 길이
    static int[] numbers = {1, 2, 3};
    static boolean[] visited = new boolean[3];
    static int[] result = new int[N];

    public static void main(String[] args) {
        backtrack(0);
    }

    public static void backtrack(int depth) {
        if (depth == N) { // 길이가 N이 되면 출력
            for (int num : result) {
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < numbers.length; i++) {
            if (!visited[i]) { // 아직 사용하지 않은 숫자라면
                visited[i] = true; // 사용 처리
                result[depth] = numbers[i]; // 현재 자리에 숫자 배치
                backtrack(depth + 1); // 다음 깊이 재귀 호출
                visited[i] = false; // 되돌아오며 원상복구 (Backtrack)
            }
        }
    }
}

🔍 출력 예시

1 2
1 3
2 1
2 3
3 1
3 2

4. 특징

• 탐색 전략: DFS 기반

• 시간 복잡도: 모든 경우의 수를 다 보는 O(n!)에 가까움
(하지만 가지치기로 일부 줄일 수 있음)

• 사용법 핵심: 조건 검사 + 방문 여부 처리 + 재귀 + 복구

5. 대표 예시 문제

6. 백트래킹 vs 완전탐색