[프로그래머스/Lv.2] 미로 탈출 - Java

문제

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

프로그래머스

시작점에서 출발하여 출구로 탈출하는 데 걸리는 최단 시간을 구하는 문제이다. 한 칸을 이동하는 데는 1초가 걸린다. 미로를 탈출하기 위해서는 레버를 반드시 거쳐야 한다.

 

리뷰

풀이

BFS로 최단 거리를 구하면 된다.

 

단, 레버를 반드시 거쳐야 출구로 나갈 수 있으므로 출구까지의 최단 거리는 시작점(S)에서 레버(L)로의 최단 거리와 레버(L)에서 출구(E)로의 최단 거리를 더한 값이다.

 

이 문제는 사실 문제에 풀이 방법이 나와 있다.

따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다.

 

BFS를 두 번 실행해야 하는데 시작점과 레버, 출구는 여러 번 지나갈 수 있다는 조건이 있으니 BFS를 실행할 때마다 방문 여부를 기록하는 배열(visited)을 초기화 해야 한다. 나는 '시작점→레버'에서 사용할 배열(visitedL)과 '레버→출구'에서 사용할 배열(visitedE)을 따로 만들었다.

 

최대한 빨리 미로를 탈출하는 데 걸리는 시간을 구하는 문제이지만 한 칸 이동하는 시간이 1초이므로 따로 시간을 처리해 줄 필요가 없다.

 

2차원 배열 형태인 미로 데이터를 다룰 때 row와 col 값을 헷갈려 런타임 에러가 발생하지 않도록 주의하자.  

 

코드

import java.util.*;

class Solution {

    String[][] maze;

    final int[] dx = {-1, 0, 1, 0};
    final int[] dy = {0, -1, 0, 1};

    int col;
    int row;

    public int solution(String[] maps) {

        int sx = 0, sy = 0, lx = 0, ly = 0, ex = 0, ey = 0;

        row = maps.length;
        col = maps[0].length();

        maze = new String[row][col];
        int[][] visitedL = new int[row][col];
        int[][] visitedE = new int[row][col];

        // maps -> maze로 변환
        // 시작점(S), 레버(L), 출구(E)의 위치를 구한다.
        for(int i=0; i<row; i++){
            maze[i] = maps[i].split("");

            int si = maps[i].indexOf("S");
            int li = maps[i].indexOf("L");
            int ei = maps[i].indexOf("E");
            if(si > -1){
                sx = si;
                sy = i;
            }
            if (li > -1) {
                lx = li;
                ly = i;
            }
            if (ei > -1) {
                ex = ei;
                ey = i;
            }
            else{
                continue;
            }
        }

        int sToL = bfs(sx, sy, lx, ly, visitedL);
        if (sToL == 0) {
            return -1;    // 출발지->레버의 최단 거리가 0이면 이동할 수 없다는 것을 의미함
        }

        int lToE = bfs(lx, ly, ex, ey, visitedE);
        if (lToE == 0) {
            return -1;
        }

        return sToL + lToE;
    }

    // BFS 함수
    private int bfs(int startX, int startY, int targetX, int targetY, int[][] visited) {
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{startX, startY});
        int distance = 0;

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

            if (x == targetX && y == targetY){
                distance = visited[y][x];
                return distance;
            }
            for(int i=0;i<4;i++) {
                int ax = x + dx[i];
                int ay = y + dy[i];

                if(ax < 0 || ax >= col || ay < 0 || ay >= row) {
                    continue;   
                }
                else if(!maze[ay][ax].equals("X") && visited[ay][ax] == 0) {
                    queue.add(new int[]{ax, ay});

                    // visited 배열에 해당 좌표까지의 거리를 기록
                    visited[ay][ax] = visited[y][x]+1;    
                }
            }
        }

        return distance;
    }
}