DFS BFS 프루닝 기법

DFS/BFS에서 프루닝 기법이란? - 문제 예시와 실전 코드 포함

프루닝(Pruning) 기법

탐색 도중 불필요하거나 정답이 될 수 없는 경로를 미리 차단함으로써 탐색 시간을 줄이는 전략

일반적인 프루닝 전략에는 다음이 포함됩니다:

1. 조건을 만족하지 않으면 더 이상 탐색하지 않기
2. 이미 더 나은 정답이 나온 상태라면 더 탐색하지 않기
3. 방문한 노드를 다시 방문하지 않기
4. 결과가 항상 나빠지는 경로 제거

효과

• 탐색 경로 수 감소: 중복되거나 더 비싼 경로는 무시
• 시간 복잡도 개선: 큐에 들어가는 노드 수 감소
• 결과의 신뢰성 유지: 정답에 영향을 주지 않으면서 성능 향상전략 설명

  DFS 프루닝	재귀호출 전에 조건 체크하여 불필요한 경로 차단
  BFS 프루닝	큐에 넣기 전에 최단 비용 조건 확인
  공통 장점	탐색 공간을 줄여 속도 개선

예제: 최소 비용으로 목표 지점 도달

• N x N 격자 지도에서 (0,0)부터 (N-1,N-1)까지 이동
  • 3 x 3 크기의 격자에서 (0, 0) 부터 (2, 2) 위치까지 이동할 때 최소 비용 경로 찾기
• 각 칸에는 이동 비용이 존재
• 상, 하, 좌, 우 이동이 가능하며, 중복 방문 허용
• 최소 비용으로 도달해야 함

DFS

💡 프루닝 조건 포인트

• if (cost >= minCost) return;
  • 현재 경로를 통해 얻는 비용이 이미 해당 지점까지 도달한 최소 비용보다 클 경우, 더이상 탐색하지 않음

package dfs_bfs;

public class GridPathPruningDFS {
    static int[][] map = { // 각 위치의 이동 비용을 담고 있는 2차원 배열 (n: 맵 크기)
        {1, 3, 1},
        {2, 1, 2},
        {4, 3, 1}
    };
    static boolean[][] visited; // 방문 여부 기록
    static int n = 3;
    static int minCost = Integer.MAX_VALUE;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) {
        visited = new boolean[n][n];
        dfs(0, 0, map[0][0], ""); // (0, 0) 부터 탐색 시작. cost: map[0][0] = 1
        System.out.println("🔚 최종 최소 비용: " + minCost);
    }

    static void dfs(int x, int y, int cost, String path) {
        path += String.format("(%d,%d) → ", x, y);

        // * 프루닝 핵심 로직 *
        if (cost >= minCost) { // 현재 경로의 누적 비용이 현재 최소 비용보다 크거나 같으면, 더 이상 탐색하지 않고 재귀 호출 중단
            System.out.printf("🚫 프루닝: %s비용 %d ≥ 최소비용 %d\\n", path, cost, minCost);
            return;
        }

        // 목표 지점 (2, 2) 에 도달하면, 누적 비용이 기존 비용보다 작을 경우 갱신
        if (x == n - 1 && y == n - 1) {
            System.out.printf("✅ 도착: %s비용 %d → 최소 갱신!\\n", path, cost);
            minCost = Math.min(minCost, cost);
            return;
        }

        visited[x][y] = true;

        // 상하좌우 기준으로 다음 위치 탐색
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            // 이미 방문한 곳은 가지 않고, 경계 조건과 방문 여부를 체크한다.
            if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny]) {
                dfs(nx, ny, cost + map[nx][ny], path);
            }
        }

        // 백트래킹 처리: DFS 는 재귀 호출이 끝나면 이전 상태로 되돌아가야 하기 때문에, 해당 위치의 방문 상태를 해제한다.
        visited[x][y] = false;
    }
}

✅ 도착: (0,0) → (0,1) → (0,2) → (1,2) → (1,1) → (1,0) → (2,0) → (2,1) → (2,2) → 비용 18 → 최소 갱신!
✅ 도착: (0,0) → (0,1) → (0,2) → (1,2) → (1,1) → (2,1) → (2,2) → 비용 12 → 최소 갱신!
🚫 프루닝: (0,0) → (0,1) → (0,2) → (1,2) → (1,1) → (2,1) → (2,0) → 비용 15 ≥ 최소비용 12
✅ 도착: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → 비용 8 → 최소 갱신!
🚫 프루닝: (0,0) → (0,1) → (1,1) → (1,2) → (2,2) → 비용 8 ≥ 최소비용 8
🚫 프루닝: (0,0) → (0,1) → (1,1) → (1,2) → (0,2) → 비용 8 ≥ 최소비용 8
🚫 프루닝: (0,0) → (0,1) → (1,1) → (1,0) → (2,0) → 비용 11 ≥ 최소비용 8
🚫 프루닝: (0,0) → (0,1) → (1,1) → (2,1) → 비용 8 ≥ 최소비용 8
✅ 도착: (0,0) → (1,0) → (1,1) → (1,2) → (2,2) → 비용 7 → 최소 갱신!
🚫 프루닝: (0,0) → (1,0) → (1,1) → (1,2) → (0,2) → 비용 7 ≥ 최소비용 7
🚫 프루닝: (0,0) → (1,0) → (1,1) → (2,1) → 비용 7 ≥ 최소비용 7
🚫 프루닝: (0,0) → (1,0) → (1,1) → (0,1) → 비용 7 ≥ 최소비용 7
🚫 프루닝: (0,0) → (1,0) → (2,0) → 비용 7 ≥ 최소비용 7
🔚 최종 최소 비용: 7

BFS

• 일반적인 BFS 는 모든 가능한 경로를 큐에 넣고 탐색하면서, 도착 지점까지 이동한다.
  • 이 방식은 간단하지만, 불필요한 경로까지 탐색할 수 있어서 비효율적이므로 프루닝 기법 적용

💡 프루닝 조건 포인트

• 현재 경로를 통해 얻는 비용이 이미 해당 지점까지 도달한 최소 비용보다 클 경우, 더이상 탐색하지 않음

if (newCost < dist[nx][ny]) {
		dist[nx][ny] = newCost;
		q.add(new Point(nx, ny, newCost));
}

• dist[nx][ny] 해당 위치까지의 최소 비용
• 새로운 경로를 통해 갱신되는 비용이 기존보다 클 경우, 큐에 넣지 않음으로써 불필요한 탐색 차단

<aside>

(0,0) → (1,0) → (1,1) → (1,2) → (2,2) 총 비용: 7

</aside>

package dfs_bfs;

import java.util.*;

public class GridPathPruningBFS {
    static int[][] map = { // 각 위치의 이동 비용을 담고 있는 2차원 배열 (n: 맵 크기)
            {1, 3, 1},
            {2, 1, 2},
            {4, 3, 1}
    };
    static int n = 3;
    static int[][] dist; // 각 위치까지 도달하는 최소 비용을 저장하는 배열

    // 방향 벡터: 상하좌우 ((x+dx[i], y+dy[i]))
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    // 상태 표현 클래스
    static class Point {
        int x, y, cost; // (x, y) 좌표, 그 위치까지의 누적 비용
        Point(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }

    public static void main(String[] args) {
        // 초기화
        dist = new int[n][n];
        for (int[] row : dist)
            Arrays.fill(row, Integer.MAX_VALUE);

        // 실행
        bfs();
        System.out.println("🔚 최종 최소 비용: " + dist[n-1][n-1]); // 도착 지점 (n-1, n-1) 의 최소 비용 출력
    }

    static void bfs() {
        // 시작 지점 (0, 0) 자기 자신의 비용으로 초기화하며, 큐에 넣어 BFS 시작
        Queue<Point> q = new LinkedList<>();
        dist[0][0] = map[0][0];
        q.add(new Point(0, 0, map[0][0]));

        // 큐가 빌 때까지 반복한다.
        while (!q.isEmpty()) {
            Point p = q.poll();
            System.out.printf("📌 탐색 중: (%d,%d), 누적 비용: %d\\n", p.x, p.y, p.cost); // 상하좌우 탐색

            for (int dir = 0; dir < 4; dir++) {
                int nx = p.x + dx[dir];
                int ny = p.y + dy[dir];

                // * 프루닝 핵심 로직 *
                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                    int newCost = p.cost + map[nx][ny];

                    // newCost 가 현재 저장된 dist[nx][ny] 보다 작을 때만 갱신
                    if (newCost < dist[nx][ny]) {
                        System.out.printf("🔄 갱신: (%d,%d) 기존 %d → 새로운 비용 %d\\n", nx, ny, dist[nx][ny], newCost);
                        dist[nx][ny] = newCost;
                        q.add(new Point(nx, ny, newCost)); // 더 나은 비용으로 도달할 수 있을 때만 큐에 추가
                    }
                }
            }
        }
    }
}

📌 탐색 중: (0,0), 누적 비용: 1
🔄 갱신: (0,1) 기존 2147483647 → 새로운 비용 4
🔄 갱신: (1,0) 기존 2147483647 → 새로운 비용 3
📌 탐색 중: (0,1), 누적 비용: 4
🔄 갱신: (0,2) 기존 2147483647 → 새로운 비용 5
🔄 갱신: (1,1) 기존 2147483647 → 새로운 비용 5
📌 탐색 중: (1,0), 누적 비용: 3
🔄 갱신: (1,1) 기존 5 → 새로운 비용 4
🔄 갱신: (2,0) 기존 2147483647 → 새로운 비용 7
📌 탐색 중: (0,2), 누적 비용: 5
🔄 갱신: (1,2) 기존 2147483647 → 새로운 비용 7
📌 탐색 중: (1,1), 누적 비용: 5
🔄 갱신: (2,1) 기존 2147483647 → 새로운 비용 8
📌 탐색 중: (1,1), 누적 비용: 4
🔄 갱신: (1,2) 기존 7 → 새로운 비용 6
🔄 갱신: (2,1) 기존 8 → 새로운 비용 7
📌 탐색 중: (2,0), 누적 비용: 7
📌 탐색 중: (1,2), 누적 비용: 7
🔄 갱신: (2,2) 기존 2147483647 → 새로운 비용 8
📌 탐색 중: (2,1), 누적 비용: 8
📌 탐색 중: (1,2), 누적 비용: 6
🔄 갱신: (2,2) 기존 8 → 새로운 비용 7
📌 탐색 중: (2,1), 누적 비용: 7
📌 탐색 중: (2,2), 누적 비용: 8
📌 탐색 중: (2,2), 누적 비용: 7
🔚 최종 최소 비용: 7