[프로그래머스] Lv.2 미로 탈출 (Java)

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

프로그래머스

 

문제 설명

1x1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 

통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다.

통로들 중 한 칸에는 exit(출구)가 있는데, 이 문은 레버를 당겨야만 열 수 있습니다.

레버도 통로 중 한 칸에 있습니다.

따라서, 출발 지점 -> 레버가 있는 칸으로 이동, 레버를 당긴 후 -> exit으로 나갈 수 있습니다.

(이때 아직 레버를 당기지 않아도 exit 칸을 지나갈 수는 있습니다.)

  한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 나가는 데 걸리는 시간을 구하려고 합니다.

 

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

---

💡 아이디어

미로를 탈출하는데 필요한 최소 시간을 구해야 하기 때문에 BFS를 사용합니다.

그리고 exit으로 탈출하기 전에 무조건 레버를 당겨야 하기 때문에,

출발점 S에서 레버에 도착 -> 레버에서 exit으로 가는 최소한의 거리(시간)을 구하면 됩니다.

---

 

📖 풀이과정

1. 주어진 maps에서 출발점 S를 찾아 위치(x,y)를 저장합니다.

 

2. S 위치에서 레버가 있는 L을 만날 때까지 최소 거리를 BFS함수로 넘겨 계산합니다.

 

3. 방문한 곳은 다시 방문하지 않도록 visited함수를 만들어줍니다.

(visited 함수를 int형으로 만들어 가는데 걸리는 시간을 여기에 저장해 줍니다.)

( **여기서 조심! 방문한 걸 확인하기 위해 시작점을 1초로 만들고 bfs를 검사합니다.)

 

4. 레버에 도착하면, 레버의 위치(x, y)와 레버까지 도착하는 데 걸린 시간을 반환합니다.

(주의! 시작점에서 시간을 1부터 설정하고 출발했기 때문에 총 걸린 시간에서 1초를 빼야 정확하게 걸린 시간이 나옵니다.)

 

 

5. 이번엔 다시 레버에서 exit에 도착할 때까지 걸리는 시간을 구하기 위해, 다시 BFS함수에 넣어 구해줍니다.

 

6. 다시 visited 함수를 초기화해 주고, E를 만날 때까지 상하좌우를 이동하면서 최소한의 시간을 구합니다.

7. 4번에서 구한 것과 마찬가지로 1초로 시작하기 때문에 구한 시간에 -1을 해서 반환합니다.

 

8. 출발점에서 레버까지 도달하는 데 걸린 시간(4번)  + 레버에서 도착점까지 도달하는데 걸린 시간(7번)을 더해서 반환합니다.

---

전체 코드

import java.util.*;
class Solution {
    static int[][] visited;//방문 확인
    static int n,m;//가로,세로 길이
    public int solution(String[] maps) {
        int answer = 0;
        
        n=maps.length; m=maps[0].length();
        
        
        int sx=0,sy=0;//시작점
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(maps[i].charAt(j)=='S'){
                    sx=i;sy=j;
                }
            }
        }
        int[] arrive = bfs(maps,sx,sy,'L'); //(sx,sy)가 'L'에 도달할 때까지 걸린 시간
        if(arrive[0]==-1) return -1;//레버에 도착하지 못하면 -1 return
        
        answer+=arrive[2];//걸린시간
        
        arrive = bfs(maps,arrive[0],arrive[1],'E');
        if(arrive[0]==-1) return -1;
        
        answer+=arrive[2];
        
        return answer;
    }
    int[] bfs(String[] maps, int sx, int sy, char end){
        
        visited = new int[n][m];//방문했는지 확인
        int[] dx={1,-1,0,0};//상하좌우
        int[] dy={0,0,1,-1};
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{sx,sy});//시작 위치
        visited[sx][sy]=1;
        
        while(!q.isEmpty()){
            int now[] = q.poll();
            
            if(maps[now[0]].charAt(now[1])==end){
                //도착x, 도착y, 걸린 시간
                return new int[]{now[0],now[1],visited[now[0]][now[1]]-1};
            }
            
            for(int i=0;i<4;i++){//상하좌우
                int nx = now[0]+dx[i];
                int ny = now[1]+dy[i];
                //이동한 좌표가
                //maps 범위를 벗어나지 않고, 벽이 아니며, 방문한 적이 없을 때
                if(nx>=0 && nx<maps.length && ny>=0 && ny<maps[0].length()
                  && maps[nx].charAt(ny)!='X' && visited[nx][ny]==0){
                    visited[nx][ny]=visited[now[0]][now[1]]+1;
                    q.add(new int[]{nx,ny});
                }
            }
        }
        return new int[]{-1};//end를 만날 수 없으면 -1리턴.
    }
}