[BOJ/Java] 9376. 탈옥

[BOJ/Java] 9376. 탈옥

https://www.acmicpc.net/problem/9376

---

🔍 문제 분석

백준 9376번 "탈옥" 문제는 2명의 죄수를 탈출시키기 위한 최단 경로를 찾는 문제이다.
벽('*')을 부수면서 이동할 수 있으며, 문의 개수가 최소인 경로를 찾아야 한다.

---

🚀 풀이 과정

이 문제는 BFS(너비 우선 탐색) + 다익스트라 유형의 접근을 해야 한다.

1. 맵의 바깥쪽에서 시작할 수 있도록 패딩을 추가한다.
   • 죄수가 문을 열고 탈출할 수도 있지만, 밖에서 열어주는 경우도 가능하기 때문.
2. BFS를 3번 수행한다.
   • 1회차: 바깥에서 BFS 수행 (외부에서 문을 여는 경우 고려)
   • 2회차: 첫 번째 죄수의 위치에서 BFS 수행
   • 3회차: 두 번째 죄수의 위치에서 BFS 수행
3. 각 BFS에서 문의 개수를 누적하여 최소값을 찾는다.
   • 모든 '.'와 'S'는 자유롭게 이동 가능.
   • ' * '(벽)은 지나갈 수 없음.
   • '#'(문)은 열면서 지나가야 하므로 비용이 증가함.
4. 세 개의 BFS 결과를 활용하여 최적의 탈출 경로를 계산한다.
   • map[i][j]에서 세 개의 BFS 값의 합을 계산.
   • 만약 map[i][j]가 문이라면, 중복으로 열린 경우가 있으므로 2번 빼야 한다.

---

💻 코드 구현

아래는 Java로 구현한 코드이다.

import java.io.*;
import java.util.*;

public class Main {
    static int h, w;
    static char[][] map;
    static int[][][] dist;
    static int[] dx = {0, 0, -1, 1}; // 좌, 우, 상, 하
    static int[] dy = {-1, 1, 0, 0}; 
    static final int INF = 10000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        while (T-- > 0) {
            // 입력 처리
            StringTokenizer st = new StringTokenizer(br.readLine());
            h = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            map = new char[h + 2][w + 2]; // 외곽 패딩 추가
            dist = new int[3][h + 2][w + 2]; // 3번 BFS 결과 저장
            List<int[]> prisoners = new ArrayList<>();

            for (int i = 0; i < h + 2; i++) {
                Arrays.fill(map[i], '.'); // 초기화
            }

            for (int i = 1; i <= h; i++) {
                String line = br.readLine();
                for (int j = 1; j <= w; j++) {
                    map[i][j] = line.charAt(j - 1);
                    if (map[i][j] == '$') {
                        prisoners.add(new int[]{i, j});
                    }
                }
            }

            // BFS 실행 (외부 + 죄수 2명)
            bfs(0, 0, 0); // 외부에서 BFS
            bfs(prisoners.get(0)[0], prisoners.get(0)[1], 1); // 첫 번째 죄수
            bfs(prisoners.get(1)[0], prisoners.get(1)[1], 2); // 두 번째 죄수

            // 최적 탈출 경로 찾기
            int answer = INF;
            for (int i = 0; i < h + 2; i++) {
                for (int j = 0; j < w + 2; j++) {
                    if (map[i][j] == '*') continue; // 벽이면 불가능
                    int totalDoors = dist[0][i][j] + dist[1][i][j] + dist[2][i][j];
                    if (map[i][j] == '#') totalDoors -= 2; // 문 중복 제거
                    answer = Math.min(answer, totalDoors);
                }
            }

            sb.append(answer).append("\n");
        }

        System.out.print(sb);
    }

    // BFS 탐색
    static void bfs(int sx, int sy, int idx) {
        for (int i = 0; i < h + 2; i++) {
            Arrays.fill(dist[idx][i], INF);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2])); // 우선순위 큐 사용
        pq.add(new int[]{sx, sy, 0});
        dist[idx][sx][sy] = 0;

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0], y = cur[1], cost = cur[2];

            if (dist[idx][x][y] < cost) continue; // 이미 더 작은 값이 존재하면 패스

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];

                if (nx < 0 || ny < 0 || nx >= h + 2 || ny >= w + 2) continue;
                if (map[nx][ny] == '*') continue; // 벽은 못 감

                int newCost = cost + (map[nx][ny] == '#' ? 1 : 0); // 문을 열면 비용 증가
                if (dist[idx][nx][ny] > newCost) {
                    dist[idx][nx][ny] = newCost;
                    pq.add(new int[]{nx, ny, newCost});
                }
            }
        }
    }
}

---

⏳ 시간 복잡도 분석

• BFS 3번 실행 → 각 BFS의 시간 복잡도는 O(hw)
• 최적 경로 탐색 → O(hw)

총 시간 복잡도는 O(3 × hw) = O(hw) 수준이므로, 최대 크기 100×100100 \times 100100×100에서도 충분히 해결 가능하다.

---

🤔 느낀점

• BFS와 다익스트라 유형의 조합을 활용하는 문제였다.
• 패딩을 추가하여 문제를 쉽게 해결할 수 있었다.
• PriorityQueue를 활용하여 BFS 탐색을 최적화하는 기법을 다시 한번 연습할 수 있었다.
• 문을 열면서 이동하는 방식을 다뤄야 했기 때문에, 단순한 BFS보다 비용을 고려하는 최단 경로 방식을 적용해야 했다.

이 문제를 통해 최단 거리와 BFS를 조합하는 유형의 문제를 확실히 연습할 수 있었다! 🚀