미로 탈출

문제

직사각형 격자 형태의 미로에서 탈출하려고 합니다. 미로를 빠져나가기 위해서는 반드시 미로 내에 있는 레버를 당긴 후 출구로 이동해야 합니다. 미로는 통로('O'), 벽('X'), 시작 지점('S'), 출구('E'), 레버('L')로 이루어져 있으며, 상하좌우로 이동할 수 있습니다. 시작 지점에서 레버를 당기고 출구로 빠져나가는 데 걸리는 최소 시간을 구하는 프로그램을 작성하는 문제입니다. 탈출할 수 없다면 -1을 반환합니다.

• 입력: 미로의 상태를 나타내는 문자열 배열 maps (가로/세로 길이 최대 100)
• 출력: 미로를 탈출하는 데 필요한 최소 시간 (불가능할 경우 -1)

링크: https://school.programmers.co.kr/learn/courses/30/lessons/159993

풀이: 2단계 BFS 최단 경로 탐색

이 문제는 '시작점 -> 레버' 구간과 '레버 -> 출구' 구간의 최단 거리를 각각 구하여 더하는 문제로 단순화할 수 있습니다. 가중치가 없는 2D 격자 탐색이므로 너비 우선 탐색(BFS)을 두 번 수행하는 것이 가장 효율적입니다.

• 좌표 탐색: 먼저 이중 반복문을 통해 시작 지점(S), 출구(E), 레버(L)의 정확한 좌표를 찾아 변수에 저장합니다.
• 공통 BFS 메서드 분리: '시작점 -> 도착점'의 최단 거리를 구하는 로직이 두 번 중복되므로, 이를 bfs라는 별도의 메서드로 분리합니다.
  • 시작 좌표와 목표 좌표를 매개변수로 받습니다.
  • visited 배열을 생성하고 시작점을 1로 초기화하여 방문 처리합니다. (0과 구분하기 위함)
  • 큐를 이용해 상하좌우 4방향을 탐색하며, 벽('X')이 아니며 아직 방문하지 않은 통로를 큐에 넣고 거리를 누적합니다.
  • 목표 좌표에 도달하면 visited에 기록된 값에서 1을 뺀 실제 이동 거리를 반환하고, 도달할 수 없다면 -1을 반환합니다.
• 결과 합산: 'S -> L' 구간의 거리를 먼저 구하고, 도달할 수 없다면 즉시 -1을 반환합니다. 도달했다면 'L -> E' 구간의 거리를 구하고, 이 역시 도달 불가라면 -1을 반환합니다. 두 구간 모두 무사히 통과했다면 두 거리를 합산하여 반환합니다.

코드

import java.util.*;

class Solution {
    int[] dy = {-1, 0, 1, 0};
    int[] dx = {0, 1, 0, -1};
    int n, m;
    
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        
        int sy = -1, sx = -1;
        int ey = -1, ex = -1;
        int ly = -1, lx = -1;
        
        // 1. 주요 지점의 좌표 찾기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char c = maps[i].charAt(j);
                if (c == 'S') {
                    sy = i; sx = j;
                } else if (c == 'E') {
                    ey = i; ex = j;
                } else if (c == 'L') {
                    ly = i; lx = j;
                }
            }
        }
        
        // 2. 시작점에서 레버까지의 최단 거리 탐색
        int toLever = bfs(sy, sx, ly, lx, maps);
        if (toLever == -1) return -1;
        
        // 3. 레버에서 출구까지의 최단 거리 탐색
        int toExit = bfs(ly, lx, ey, ex, maps);
        if (toExit == -1) return -1;
        
        // 4. 총 소요 시간 반환
        return toLever + toExit;
    }
    
    // 시작점부터 목표점까지의 최단 거리를 반환하는 공통 BFS 메서드
    private int bfs(int startY, int startX, int targetY, int targetX, String[] maps) {
        Queue<Node> q = new LinkedList<>();
        int[][] visited = new int[n][m];
        
        q.add(new Node(startY, startX));
        visited[startY][startX] = 1;
        
        while (!q.isEmpty()) {
            Node node = q.poll();
            
            // 목표 지점에 도달한 경우 탐색 종료 및 거리 반환
            if (node.y == targetY && node.x == targetX) {
                return visited[node.y][node.x] - 1;
            }
            
            for (int i = 0; i < 4; i++) {
                int ny = node.y + dy[i];
                int nx = node.x + dx[i];
                
                if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                if (visited[ny][nx] != 0 || maps[ny].charAt(nx) == 'X') continue;
                
                q.add(new Node(ny, nx));
                visited[ny][nx] = visited[node.y][node.x] + 1;
            }
        }
        
        return -1; // 도달 불가능한 경우
    }
    
    class Node {
        int y, x;
        Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

알고리즘 분류

그래프 탐색 (Graph Traversal), 너비 우선 탐색 (BFS)