[프로그래머스] 미로 탈출 (Java) - BFS

📌 핵심 요약

• 경유지 최단거리 분해 — "S에서 E로 가되 반드시 L을 거쳐야 한다"는 조건은 S→L 최단거리 + L→E 최단거리로 쪼갤 수 있다. 경유지가 고정이면 두 BFS 결과를 독립적으로 합쳐도 최단이 보장된다.
• BFS는 target 문자만 알면 된다 — 목표 좌표를 미리 저장할 필요 없이, 탐색 중 처음 만난 target까지의 거리가 곧 최단거리다.

 

목차

1 문제 분석

Programmers #159993

미로 탈출

5 ≤ 세로 · 가로 ≤ 100 · Lv.2

난이도: Level 2

S(시작점)에서 출발해 E(출구)로 탈출해야 한다. 단, 출구는 잠겨 있어서 반드시 L(레버)을 먼저 당겨야 열린다. X는 벽이라 지나갈 수 없고, 한 칸 이동에 1초가 걸린다. 탈출까지 걸리는 최소 시간을 구하고, 탈출할 수 없으면 -1을 반환한다.

풀이 과정

1. 미로를 순회하며 S와 L의 좌표를 기록한다. (E는 BFS가 문자로 직접 찾으므로 저장 불필요)
2. 1차 BFS: S에서 출발해 L까지의 최단거리를 구한다. 도달 불가면 -1 반환.
3. 2차 BFS: L에서 출발해 E까지의 최단거리를 구한다. 도달 불가면 -1 반환.
4. 두 최단거리의 합을 반환한다.

2 접근: BFS를 두 번으로 나누기

이 문제의 핵심은 "레버를 거쳐야 한다"는 제약을 어떻게 처리하느냐다.

상태에 레버를 당겼는지 여부를 추가해서 한 번의 BFS로 풀 수도 있지만, 훨씬 단순한 관점이 있다.

경유지 L이 고정되어 있다는 점에 주목하면, 전체 경로는 반드시 "S에서 L까지의 구간"과 "L에서 E까지의 구간"으로 나뉜다. 각 구간의 최단거리는 서로 독립적이므로, 두 구간을 각각 BFS로 구해 더하면 그것이 전체 최단 시간이 된다.

ℹ️

왜 두 최단거리를 더해도 최단이 보장될까?

전체 경로가 L을 지나는 순간, 경로는 (S→L 부분)과 (L→E 부분)으로 쪼개진다. 만약 전체 최단 경로의 S→L 부분이 S→L 최단거리보다 길다면, 그 부분만 최단 경로로 교체해서 더 짧은 전체 경로를 만들 수 있으므로 모순이다. 따라서 각 구간의 최단거리 합 = 전체 최단거리가 성립한다. 경유지가 하나로 고정일 때만 통하는 논리라는 점에 주의.

또 하나의 설계 포인트는 BFS에 목표 좌표가 아닌 목표 문자를 넘긴다는 것이다.

BFS는 거리 순으로 칸을 방문하므로, 탐색 중 target 문자를 처음 만난 시점의 거리가 곧 최단거리다.

덕분에 E의 좌표를 미리 저장할 필요가 없고, 같은 bfs 메서드를 두 구간에 그대로 재사용할 수 있다.

3 전체 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    // 상하좌우 4방향 이동량 (행 변화, 열 변화)
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};

    public int solution(String[] maps) {
        int rows = maps.length;
        int cols = maps[0].length();

        char[][] map = new char[rows][cols];
        int[] start = null;   // 시작 지점 S 좌표
        int[] lever = null;   // 레버 L 좌표

        // 문자열 배열 → char 2차원 배열 변환하며 S, L 좌표 기록
        // (E는 BFS가 target 문자로 직접 찾으므로 좌표 저장 불필요)
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char c = maps[i].charAt(j);
                map[i][j] = c;

                if (c == 'S')      start = new int[]{i, j};
                else if (c == 'L') lever = new int[]{i, j};
            }
        }

        // 1차 BFS: 시작점 → 레버 최단거리
        int toLever = bfs(start, 'L', map);
        if (toLever == -1) return -1;   // 레버 도달 불가 → 탈출 불가

        // 2차 BFS: 레버 → 출구 최단거리
        int toExit = bfs(lever, 'E', map);
        if (toExit == -1) return -1;    // 출구 도달 불가 → 탈출 불가

        // 경유지(L)가 고정이므로 두 최단거리의 합이 전체 최단 시간
        return toLever + toExit;
    }

    /** start 좌표에서 target 문자까지의 최단거리 반환 (도달 불가 시 -1) */
    private int bfs(int[] start, char target, char[][] map) {
        int rows = map.length;
        int cols = map[0].length;

        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[rows][cols];

        // 큐 원소는 {행, 열, 시작점부터의 거리}
        queue.add(new int[]{start[0], start[1], 0});
        visited[start[0]][start[1]] = true;   // 방문 표시는 enqueue 시점에!

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int row = cur[0], col = cur[1], dist = cur[2];

            // 목표 도달 → BFS 특성상 처음 만난 거리가 곧 최단거리
            if (map[row][col] == target) return dist;

            for (int d = 0; d < 4; d++) {
                int nextRow = row + dx[d];
                int nextCol = col + dy[d];

                // 격자 범위를 벗어나면 스킵
                if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) continue;
                // 벽(X)이면 스킵
                if (map[nextRow][nextCol] == 'X') continue;
                // 이미 방문한 칸이면 스킵
                if (visited[nextRow][nextCol]) continue;

                visited[nextRow][nextCol] = true;
                queue.add(new int[]{nextRow, nextCol, dist + 1});
            }
        }

        return -1;   // 큐가 비었는데 target 미도달
    }
}

💡

방문 표시는 queue 삽입 직전에

방문 표시를 poll 시점에 하면 같은 칸이 큐에 여러 번 들어가 시간과 메모리를 낭비한다. "확인 → 방문 표시 → 큐 삽입" 순서를 지켜, 큐에 넣는 순간 방문 처리하는 것이 BFS의 기본 패턴이다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.