[프로그래머스] 미로 탈출 - Java 자바

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

프로그래머스

개념: bfs, 그래프 탐색

 

 

문제

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

 

미로 예시

 

 

풀이

시작점에서 레버까지 이동한 후, 레버에서 출구까지 이동해야 한다.

따라서 각각 최소 시간을 구하여 더해준다. 

 

import java.util.ArrayDeque;

class Solution {
    static int n, m;
    static int[] start, end, lever;
    static char[][] map;
    static int[][] dist;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();       
        map = new char[n][m];
        for (int i = 0; i < n; i++) {
            map[i] = maps[i].toCharArray();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'S') {
                    start = new int[] {i, j};
                } else if (map[i][j] == 'E') {
                    end = new int[] {i, j};
                } else if (map[i][j] == 'L') {
                    lever = new int[] {i, j};
                }
            }
        }

        int startToLever = bfs(start, lever);
        int leverToEnd = bfs(lever, end);

        if (startToLever == -1 || leverToEnd == -1) {
            return -1;
        } else {
            return startToLever + leverToEnd;
        }
    }

    public static int bfs(int[] start, int[] end) {
        dist = new int[n][m];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        dist[start[0]][start[1]] = 1;
        q.add(start);

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

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

                // 범위 벗어난 경우
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                    continue;
                }

                // 이미 방문한 경우
                if (dist[nx][ny] > 0) {
                    continue;
                }

                // 벽인 경우
                if (map[nx][ny] == 'X') {
                    continue;
                }

                dist[nx][ny] = dist[x][y] + 1;
                q.add(new int[]{nx, ny});

                // end 지점에 도달
                if (nx == end[0] && ny == end[1]) {
                    return dist[nx][ny] - 1;
                }
            }
        }

        return -1;
    }
}