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

코린·2023년 6월 28일

알고리즘

목록 보기

20/44

문제 설명

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

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

제한사항

5 ≤ maps의 길이 ≤ 100
- 5 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
  - S : 시작 지점
  - E : 출구
  - L : 레버
  - O : 통로
  - X : 벽
- 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
- 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

입출력 예

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

문제풀이

BFS 를 사용해서 푸는 문제입니다.

잘못생각한점

레버가 있기 때문에 레버까지 탐색하는 것, 레버에서 출구까지 탐색하는 것 총 두 번 탐색해야 합니다. 맵의 모양이 정사각형이 아닙니다. 직사각형이기 때문에 가로와 세로 길이를 따로 생각해주어야 합니다.

결과 코드

참고블로그

function solution(maps) {
    var answer = 0;
    
    let dx=[-1,1,0,0];
    let dy=[0,0,-1,1];
    let n= maps.length;
    let m= maps[0].length;
    
    //bfs 함수
    function bfs(start, end, visited){
        
        let [x,y] = start;
        let queue = [];
        visited[x][y]=1;
        queue.push([x,y]);
        
        while(queue.length){
            let [cx,cy] = queue.shift();
            
            for(let dir =0 ;dir < 4; dir++){
                let nextX = cx + dx[dir];
                let nextY = cy + dy[dir];
                
                //범위를 벗어나는 경우
                if(nextX < 0 || nextX >=n || nextY <0 || nextY >= m) continue;
                //탐색할 수 없는 곳인 경우
                if(maps[nextX][nextY] === 'X' || visited[nextX][nextY] !== 0) continue;
                //출구인 경우
                if(nextX === end[0] && nextY === end[1]){
                    return visited[cx][cy];
                }
                
                visited[nextX][nextY] = visited[cx][cy] + 1;
                queue.push([nextX,nextY]);
            }
        }
        
    }
    

    let start = [];
    let end = [];
    let lever =[];
    
    
    for(let i = 0; i < n;i++){
        for(let j=0;j< m;j++){
            if(maps[i][j] === 'S'){start = [i,j];}
            else if(maps[i][j] === 'E'){end = [i,j];}
            else if(maps[i][j] === 'L'){lever = [i,j];}
            
        }
    }
    
    let visited = Array.from(Array(n), ()=> Array(m).fill(0));
    let visited2 = Array.from(Array(n), ()=> Array(m).fill(0));
    
    //레버까지 탐색하는 경우
    let cnt1 = bfs(start,lever,visited);
    //레버에서 출구까지
    let cnt2 = bfs(lever,end,visited2);
    
    return cnt1 && cnt2 ? cnt1+cnt2 : -1;
}