[알고리즘] 백트래킹(Backtracking)

1. 백트래킹(Backtracking)이란?

백트래킹은 결정적 문제를 해결하기 위한 알고리즘 설계 기법으로, 모든 가능한 후보 해를 체계적으로 탐색하며, 불가능한 해답일 경우 이전 단계로 돌아가 다른 경로를 탐색한다.

---

2. 백트래킹의 특징

1. 완전 탐색 기법의 일종

• 모든 경우의 수를 탐색하지만, 불필요한 경로를 가지치기(Pruning)하여 효율성을 높인다.

2. DFS(깊이 우선 탐색) 기반

• 재귀를 활용하여 상태 공간 트리를 탐색한다.

3. 가지치기(Pruning)

• 불가능하거나 최적해가 될 가능성이 없는 경로를 조기에 배제하여 탐색 시간을 단축한다.

---

3. 백트래킹의 동작 원리

1. 현재 상태에서 가능한 모든 선택을 시도한다.

2. 각 선택에 대해 재귀적으로 탐색을 수행한다.

3. 조건에 부합하지 않는 경우, 이전 상태로 돌아간다(백트래킹)

4. 문제의 해답을 찾거나 탐색 가능한 모든 경로를 확인할 때까지 반복한다.

---

4. 백트래킹의 장단점

장점

• 가능한 모든 해를 탐색하므로 정확한 해를 보장한다.
• 문제의 구조를 단순화하여 구현 가능

단점

• 상태 공간 클 경우, 탐색 시간이 급격히 증가할 수 있다.
• 가지치기가 적절하지 않으면 비효율적

---

5. 백트래킹의 시간 복잡도

• 시간 복잡도는 문제의 상태 공간 크기에 따라 결정되며, 최악의 경우 O(b^d) (b는 선택지의 개수, d는 탐색 깊이)이다.
• 효율적인 가지치기를 통해 탐색 시간을 줄일 수 있다.

---

6. 백트래킹의 활용 예시

1. 조합 문제

• 예: N-Queen 문제, Sudoku 풀이

2. 최적화 문제

• 예: 부분 집합 합 문제, 배낭 문제(Knapsack Problem)

3. 그래프 탐색 문제

• 예: Hamiltonian Cycle, 그래프 색칠하기

4. 퍼즐 문제

• 예: 미로 찾기, 8퍼즐 문제

---

7. 백트래킹의 구현 예제

예제 1: N-Queen 문제

문제: N x N 체스판 위에 N개의 퀸을 배치하되, 서로 공격하지 못하도록 배치하는 경우의 수를 구하라.

public class NQueen {
    private static int count = 0;

    public static void main(String[] args) {
        int N = 8; // 체스판 크기
        int[] board = new int[N];
        solve(board, 0, N);
        System.out.println("Total solutions: " + count);
    }

    private static void solve(int[] board, int row, int N) {
        if (row == N) {
            count++;
            return;
        }
        for (int col = 0; col < N; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col; // 퀸 배치
                solve(board, row + 1, N); // 다음 행으로 이동
                board[row] = 0; // 백트래킹
            }
        }
    }

    private static boolean isSafe(int[] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col || Math.abs(board[i] - col) == row - i) {
                return false; // 같은 열 또는 대각선
            }
        }
        return true;
    }
}

 

해설:

• isSafe 함수는 현재 위치가 안전한지 확인.
• 퀸을 배치한 뒤, 다음 행으로 이동하며 백트래킹 수행.

 

 

예제 2: 부분 집합 합 문제 (Subset Sum Problem)

문제: 주어진 배열에서 특정 합을 이루는 부분 집합을 구하라.

import java.util.*;

public class SubsetSum {
    public static void main(String[] args) {
        int[] nums = {3, 34, 4, 12, 5, 2};
        int target = 9;
        List<Integer> subset = new ArrayList<>();
        if (backtrack(nums, 0, target, subset)) {
            System.out.println("Subset found: " + subset);
        } else {
            System.out.println("No subset found");
        }
    }

    private static boolean backtrack(int[] nums, int index, int target, List<Integer> subset) {
        if (target == 0) return true;
        if (index >= nums.length || target < 0) return false;

        subset.add(nums[index]);
        if (backtrack(nums, index + 1, target - nums[index], subset)) {
            return true;
        }
        subset.remove(subset.size() - 1); // 백트래킹

        return backtrack(nums, index + 1, target, subset);
    }
}

 

해설:

• 재귀적으로 부분 집합을 탐색하며, 목표 합에 도달하지 못하면 백트래킹.

---

백트래킹은 효율적인 완전 탐색을 가능하게 하는 알고리즘 설계 기법이다.

다양한 문제에 적용 가능하지만, 상태 공간의 크기와 가지치기 기법의 적합성을 고려해야 한다