완전탐색(재귀) - 백트래킹, pruning

완전탐색(Exhaustive Search) – 재귀와 의사결정 트리

완전탐색은 가능한 모든 해를 확인하여 정답을 찾는 알고리즘 패러다임
이를 이해하기 쉽게 표현하는 방식 중 하나가 의사결정 트리(Decision Tree)

1. 의사결정 트리와 DFS

의사결정 트리는 문제 해결을 위한 모든 선택지를 트리 형태로 표현한 것
트리의 루트에서 시작하여 모든 리프 노드에 도달하면 가능한 모든 해를 탐색할 수 있다.

이 과정은 보통 DFS(Depth-First Search, 깊이 우선 탐색) 방식으로 구현된다.

예: [1, 2, 3]의 모든 순열

            []
      /      |      \
    [1]     [2]     [3]
   /   \    /   \   /   \
[1,2] [1,3][2,1][2,3][3,1][3,2]
   |      |    |     |    |     |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

트리의 각 경로는 하나의 가능한 해를 나타내며, DFS로 탐색하면 모든 경우를 확인할 수 있다.

2. Backtracking(백트래킹)

백트래킹은 DFS 탐색 중에 상태를 원래대로 되돌리는 과정
예를 들어, 한 경로 탐색이 끝난 후 다른 선택지를 탐색하기 위해 이전 상태로 돌아가는 것이 필요하다.

동작 원리

1. 선택 가능한 후보 중 하나를 선택하고 탐색 진행
2. 탐색이 끝나면 해당 선택을 취소(원래 상태 복원)
3. 다른 후보를 선택해 탐색 반복

이 과정을 통해 모든 경우를 빠짐없이 확인할 수 있다.

예제 코드 – 순열 생성

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        boolean[] visited = new boolean[nums.length];
        dfs(new ArrayList<>(), visited, nums);
    }

    static void dfs(List<Integer> path, boolean[] visited, int[] nums) {
        if (path.size() == nums.length) {
            System.out.println(path);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                path.add(nums[i]);
                dfs(path, visited, nums);
                path.remove(path.size() - 1);  // 상태 복원
                visited[i] = false;
            }
        }
    }
}

핵심:

• visited[i] = true → 해당 숫자 선택
• 재귀 호출 후 → visited[i] = false (상태 복원)
  이 과정을 통해 모든 순열을 생성할 수 있다.

3. Pruning(가지치기)

Pruning(가지치기) 는 탐색 과정에서 불필요한 경우를 미리 제외하여 탐색 속도를 최적화하는 기법
예를 들어, N-Queen 문제에서 이미 공격 가능한 위치에 퀸이 있으면 탐색을 더 진행할 필요가 없다.

예제 – N-Queen (Pruning 적용)

import java.util.*;

public class NQueens {
    static List<int[]> solutions = new ArrayList<>();

    public static void main(String[] args) {
        int n = 4;
        solve(new int[n], 0, n);
        for (int[] sol : solutions) System.out.println(Arrays.toString(sol));
    }

    static void solve(int[] board, int row, int n) {
        if (row == n) {
            solutions.add(board.clone());
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col;
                solve(board, row + 1, n);  // 다음 행 탐색
                board[row] = -1;           // 백트래킹
            }
        }
    }

    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) == Math.abs(row - i))
                return false;
        }
        return true;
    }
}

• Backtracking: 모든 행에 대해 가능한 열을 탐색
• Pruning: isSafe()를 이용해 유효하지 않은 경우를 미리 배제