[프로그래머스 / Java] 미로 탈출

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

프로그래머스

---

◎ 문제

---

◎ 코드 및 풀이

 

import java.util.*;

public class Solution {
    static int X, Y;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        Solution sol = new Solution();
        int result1 = sol.solution(new String[]{"SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"});
        int result2 = sol.solution(new String[]{"LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"});
        System.out.println(result1 == 16 ? "테스트 통과" : "테스트  실패");
        System.out.println(result2 == -1 ? "테스트 통과" : "테스트  실패");
    }
    /*
    S : 시작 지점
    E : 출구
    L : 레버
    O : 통로
    X : 벽
    */

    static int sx, sy, ex, ey, rx, ry, value;

    public int solution(String[] maps) {
        X = maps[0].length();
        Y = maps.length;

        int sx = -1, sy = -1; // 시작 지점
        int ex = -1, ey = -1; // 출구
        int lx = -1, ly = -1; // 레버

        // 좌표 찾기
        for (int i = 0; i < Y; i++) {
            for (int j = 0; j < X; j++) {
                char c = maps[i].charAt(j);
                if (c == 'S') {
                    sx = j; sy = i;
                } else if (c == 'E') {
                    ex = j; ey = i;
                } else if (c == 'L') {
                    lx = j; ly = i;
                }
            }
        }

        // BFS로 최단거리 구하기
        int dist1 = bfs(maps, sx, sy, lx, ly); // S → L
        int dist2 = bfs(maps, lx, ly, ex, ey); // L → E

        if (dist1 == -1 || dist2 == -1) return -1;
        return dist1 + dist2;
    }

    // BFS: 최단 거리 구하기
    int bfs(String[] maps, int sx, int sy, int ex, int ey) {
        if (sx == -1 || sy == -1 || ex == -1 || ey == -1) return -1;

        boolean[][] visited = new boolean[Y][X];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{sx, sy, 0});
        visited[sy][sx] = true;

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

            if (x == ex && y == ey) return v; // 도착

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

                if (nx < 0 || ny < 0 || nx >= X || ny >= Y) continue;
                if (visited[ny][nx]) continue;
                if (maps[ny].charAt(nx) == 'X') continue; // 벽

                visited[ny][nx] = true;
                q.add(new int[]{nx, ny, v + 1});
            }
        }
        return -1; // 도달 불가
    }
}

---

◎ 기록

DFS는 최단 경로를 보장하지 못합니다. 그러나 BFS는 첫 도착 시점이 최단거리로 보장됩니다.

따라서, Queue를 활용한 BFS를 선택했습니다.

또한 레버를 당겨야 탈출할 수 있는 문제이기 때문에 S → L, L → E 총 두 번의 BFS를 실행해 도달 가능 여부를 판단 후 두 값을 더해 반환하는 것으로 풀이를 끝냈습니다.