프로그래머스 Level2 미로 탈출 java 풀이

 

문제 설명

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

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

 

제한사항

• 5 ≤ maps의 길이 ≤ 100

 

입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

입출력 예 설명

입출력 예 #1

주어진 문자열은 다음과 같은 미로이며

 

다음과 같이 이동하면 가장 빠른 시간에 탈출할 수 있습니다.

 

4번 이동하여 레버를 당기고 출구까지 이동하면 총 16초의 시간이 걸립니다. 따라서 16을 반환합니다.

입출력 예 #2

주어진 문자열은 다음과 같은 미로입니다.

 

시작 지점에서 이동할 수 있는 공간이 없어서 탈출할 수 없습니다. 따라서 -1을 반환합니다.

 

풀이

 

import java.util.*;
 
class Solution {
    
    int startX;
    int startY;
    
    int exitX;
    int exitY;
    
    int reStartX;
    int reStartY;
    
    int lX;
    int lY;
    
    int []dx = {-1,0,1,0};
    int []dy = {0,1,0,-1};
    
    public class Location{
        int x;
        int y;
        int depth;
        
        Location(int x, int y, int depth){
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }
    
    
    public void setSEL(String[] maps){
        for(int i = 0 ; i < maps.length; i++){
            for(int j = 0 ; j < maps[i].length(); j++){
                
                if(maps[i].charAt(j) == 'S'){
                    startX = j;
                    startY = i;
                }
                
                if(maps[i].charAt(j) == 'E'){
                    exitX = j;
                    exitY = i;
                }
                
                if(maps[i].charAt(j) == 'L'){
                    lX = j;
                    lY = i;
                }
            }
        }
    }
    
    public int bfsToL(String[] maps, int[][] visited){
        
        Queue<Location> q = new LinkedList<>();
        q.add(new Location(startX,startY,0));
        visited[startY][startX] = 1;

        
        while(!q.isEmpty()){
            Location curLocation = q.poll();
            int cx = curLocation.x;
            int cy = curLocation.y;
            int cDepth = curLocation.depth;
            
            if(maps[cy].charAt(cx) == 'L'){
                reStartX = cx;
                reStartY = cy;
                return cDepth;
            }
            
            for(int i = 0 ; i < 4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                if( ny >= 0 && ny < maps.length && nx >= 0 && nx < maps[0].length() && maps[ny].charAt(nx) != 'X' && visited[ny][nx] == 0){
                    q.add(new Location(nx,ny,cDepth+1));
                    visited[ny][nx] = 1;

                }
            }
            
        }
        return -1;   
    }
    
    public int bfsToE(String[] maps, int[][] visited){
        
        Queue<Location> q = new LinkedList<>();
        q.add(new Location(reStartX,reStartY,0));
        visited[reStartY][reStartX] = 1;
        
        while(!q.isEmpty()){
            Location curLocation = q.poll();
            int cx = curLocation.x;
            int cy = curLocation.y;
            int cDepth = curLocation.depth;
            
            
            if(maps[cy].charAt(cx) == 'E'){
                return cDepth;
            }
            
            for(int i = 0 ; i < 4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                if( ny >= 0 && ny < maps.length && nx >= 0 && nx < maps[0].length() && maps[ny].charAt(nx) != 'X' && visited[ny][nx] == 0){
                    q.add(new Location(nx,ny,cDepth+1));
                    visited[ny][nx] = 1;
                }
            }
            
        }
        return -1;   
    }
    
    
    
    public int solution(String[] maps) {
        //최단경로 2번 돌리기 bfs

        int secondToL = 0;
        int secondToE = 0;
        int [][] visited1 = new int[101][101];
        int [][] visited2 = new int[101][101];
        
        setSEL(maps);
        
        secondToL = bfsToL(maps,visited1);
        
        if(secondToL == -1){
            return -1;
        }
        
        secondToE = bfsToE(maps,visited2);
        
        // System.out.print(secondToL + " " + secondToE);
        
        if(secondToE == -1){
            return -1;
        }
        
        int answer = secondToL + secondToE;
        return answer;
    }
}

 

 

개선점 

 

1. 함수에 visited를 직접 넣어 얕은 복사가 발생했다. 한번 수정된 값이 중복으로 전달되어 내가 원하는 대로 visited가 동작하지 않았다. bfs를 할 경우 내부에서 직접 visited를 선언해 보자.

2. 2개의 함수로 나눌 필요가 없었다. 하나의 함수에서 target 인자를 받아서 처리해 보자

3. visited를 체크할 때 큐에서 꺼낼 때마다 체크를 하는 것이 아니라 큐를 등록할 때만 하지 않으면 시간 초과가 난다. 큐가 이동할 위치를 방문처리 하는 것이 아닌 큐가 꺼내진 즉 현재 위치를 방문처리 하게 된다면 다음 위치를 방문처리 하지 못해 큐가 꺼내졌을 때 중복된 곳을 방문할 수 있으므로 시간 초과가 날 수 있다. 주의할 것