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

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

백트래킹은 완전 탐색의 한 방법으로, 가능한 모든 경우를 탐색하지만, 불필요한 경로를 조기에 배제(가지치기, Pruning)하여 효율성을 높이는 알고리즘이다.

• 기본 아이디어: 현재 상태에서 유망하지 않은 경로를 탐색하지 않고 이전 단계로 돌아가 다른 경로를 시도
• 특징
  - DFS(깊이 우선 탐색)를 기반으로 함
  - 가지치기 기법을 활용해 탐색 공간을 줄임
• 장단점
  - 장점
     - 가능한 모든 해를 탐색하므로 정확한 해를 보장
     - 문제의 구조를 단순화하여 구현 가능
  - 단점
     - 상태 공간이 클 경우, 탐색 시간이 급격히 증가
     - 가지치기가 적절하지 않으면 비효율적
• 시간 복잡도
  - 시간 복잡도는 문제의 상태 공간 크기에 따라 결정되며, 최악의 경우 O(b ^ d) (b는 선택지의 개수, d는 탐색 깊이)이다.
  - 효율적인 가지치기(Pruning)를 통해 탐색 시간을 단축할 수 있다.

---

2. 백트래킹의 주요 구성 요소

1. 상태 공간 트리(State Space Tree)

• 문제를 해결하기 위해 탐색해야 하는 모든 가능한 경로를 트리 구조로 표현

2. 유망성 판단(Feasibility Check)

• 현재 상태가 문제를 해결할 가능성이 있는지 검사
• 유망하지 않은 경로는 더 이상 탐색하지 않고 가지치기

3. 종료 조건(Base Case)

• 탐색이 끝났거나 해답을 찾은 경우 종료

---

3. 백트래킹의 동작 원리

1. 현재 노드에서 가능한 모든 선택을 시도

2. 선택한 경로를 따라가며 조건에 맞는지 검사

3. 조건에 맞지 않으면 해당 경로를 백트래킹하여 이전 상태로 돌아감

4. 모든 경로를 탐색하거나 해답을 찾을 때까지 반복

---

4. 백트래킹의 구현 예제

예제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;
    }
}

 

출력:

Total solutions: 92(8-Queen의 경우)

 

 

예제2: 부분 집합 합 문제

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

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);
    }
}

 

출력:

Subset found: [4, 5]

---

5. 백트래킹의 활용 예시

1. 조합 문제

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

2. 최적화 문제

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

3. 그래프 탐색 문제

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

4. 퍼즐 문제

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