[JS] 2Level / 연습문제 / 미로 탈출

문제 설명

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

프로그래머스

 

문제 풀이 방법

이 문제는 최단 길이를 구하는 문제이기에 BFS가 적절하다 생각해 풀었다.

 

시작 지점과 레버, 출구 지점을 주어진 맵에서 구하고 문제를 풀이할 BFS 함수를 구현했다.

 

BFS함수를 구현할 때 햇갈렸다고 느낀 부분이 값의 반환 시점이다.

어떤 방밥으로도 도달 하고자 하는 지점까지 갈 수 없을 때, -1을 반환해야하는데 이 -1을 반환하는 타이밍을 정하는 것이 햇갈렸다.

-은 while 문이 끝났음에도 불구하고 지금까지 이동한 move값이 반환되지 않았다면 -1을 반환하는 것으로 구현했다.

 

코드

const solution = (maps) => {
    let answer = 0;
    let yL = maps.length;
    let xL = maps[0].length;
    let rotaX = [0, 0, -1, 1];
    let rotaY = [-1, 1, 0, 0];
    let dic = {
        'S': [],
        'L': [],
        'E': []
    }
    
    
    // 1. 시작, 레버, 출구 지점의 좌표를 파악
    maps.forEach((el, idx) => {
        el.split('').forEach((e, i) => {
            if(e === 'S' || e === 'L' || e === 'E'){
                dic[e] = [idx, i];
            }
        })
    });
    
    // 2. 최단 거리를 찾는 로직 구성(시작, 끝 지점을 인자로 전달 => 시간 반환)
    const find = (s, e, map) => {
        let newMap = Array.from({length: yL}, () => Array(xL).fill(false));
        let que = [[...s, 0]];
        let cnt = 0;
        
        while(que.length){
            let [curY, curX, move] = que.shift();
            newMap[curY][curX] = true;
            
            if(curY === e[0] && curX === e[1]) {
                return move;
            }
            for(let i=0; i<4; i++){
                let nextY = curY + rotaY[i];
                let nextX = curX + rotaX[i];
                 
                if(nextY >= 0 && 
                   nextX >= 0 && 
                   nextY < yL && 
                   nextX < xL && 
                   maps[nextY][nextX] !== 'X' && 
                   !newMap[nextY][nextX]
                  ) {
                    que.push([nextY, nextX, move + 1]);
                    newMap[nextY][nextX] = true;
                }
            }
        }
        // 갈 수 있는 길이 없는 경우
        return -1
    }
    const t1 = find(dic['S'], dic['L'], answer);
    const t2 = find(dic['L'], dic['E'], answer);
    
    // 3. 답 반환
    return (t1 === -1 || t2 === -1) ? -1 : t1 + t2;
}