[Programmers / JS] Lv.2 미로 탈출

문제 설명

제한 사항

입출력 예

 

Solve

• 어떤 맵이 존재하고 최단 거리를 구해야한다면 BFS를 가장 먼저 생각합니다.
• 레버를 꼭 거치고 난 후 출구에 도착해야 하기 때문에 "시작 지점에서 부터 레버까지의 거리 + 레버에서부터 출구까지의 거리"를 구해야합니다.
• BFS를 구현하고 각각 시작지점과 레버, 레버와 출구의 좌표를 넣어 거리를 구한 후 더하여 결과값을 리턴해주었습니다.
• 둘 중에 하나라도 거리값이 0이라면 탈출할 수 없는 경우이기 때문에 예외처리 하였습니다.

Code

function solution(maps) {
    let answer = 0;
    const col = maps.length;
    const row = maps[0].length;
    let start = null;
    let lever = null;
    let exit = null;
    
    for(let i = 0 ; i < col; i++) {
        for(let j = 0 ; j < row; j++) {
            if(maps[i][j] === "S") start = [i, j];
            if(maps[i][j] === "L") lever = [i, j];
            if(maps[i][j] === "E") exit = [i, j];
        }
    }
    const dx = [-1, 0, 1, 0];
    const dy = [0 ,1, 0, -1];
    // 시작지점에서 레버까지의 거리 + 레버에서 도착지까지의 거리
    
    const bfs = (start, end) => {
        const visited = Array.from({length: col}, ()=>Array.from({length: row}, ()=> 0));
        const [sx, sy] = start;
        const [ex, ey] = end;
        const queue = [];
        visited[start] = 1;
        
        queue.push([sx, sy]);
        
        while(queue.length) {
            const [x, y] = queue.shift();
            if(x === ex && y === ey) break;
            for(let i = 0 ; i < 4; i++) {
                const nx = dx[i] + x;
                const ny = dy[i] + y;
                
                if(nx < 0 || ny < 0 || nx >= col || ny >= row) continue;
                if(maps[nx][ny] === "X") continue;
                if(visited[nx][ny] < 1) {
                    visited[nx][ny] = visited[x][y] + 1;
                    queue.push([nx, ny]);
                }
            }
        }
        return visited[ex][ey];
    }
    
    const startToLever = bfs(start, lever);
    const leverToExit = bfs(lever, exit);
    
    if(!startToLever || !leverToExit) return -1;
    return startToLever + leverToExit;
    
}