프로그래머스 level 2 - 미로 탈출(Javascript)

프로그래머스 level 2 - 미로 탈출

배운 것, 유의할 것

• 레버를 방문했다가 방문 배열과 큐를 초기화한 후 출구로 가는 것만 생각할 수 있다면 전형적인 그래프 탐색 문제였고, BFS로 어렵지않게 풀 수 있었다.
• 그렇지만 방문배열과 큐를 초기화하는 과정에서 break 가 아닌 continue 를 쓰는 바람에 한참의 시간을 쏟아버림…
• 문제의 코드는 상하좌우를 확인하면서 레버를 방문하면 방문배열과 큐를 초기화해주는데, 코드를 짜면서 처음에는 continue를 사용했다. 다음 while문이 시작될 것 처럼 생각했던 것 같다.
• 그치만 이 때문에 위쪽 통로를 탐색하면서 레버를 발견해서 초기화되면서 '하좌우’에서 통로를 만나면 바로 방문처리를 해버리면서 문제가 발생했었다.

            for(let i = 0; i < 4; i++){
                const nr = row + dr[i];
                const nc = col + dc[i];
                if(nr >= 0 && nr < maps.length && nc >= 0 && nc < maps[0].length
                 && !visited[nr][nc] && maps[nr][nc] !== 'X'){
                    // 레버를 처음 방문하는 경우
                    // 방문 배열을 초기화해주고, 방문 flag를 true로, 큐도 초기화
                    if(maps[nr][nc] === 'L' && !visitedLever){
                        visited = maps.map(arr => arr.map(v => false));
                        visited[nr][nc] = true;
                        visitedLever = true;
                        q = [];
                        q.push([nr, nc, count + 1, visitedLever])
                        break; // continue가 아닌 break와야함!!
                    }
                    // 레버통로 방문 flag가 true일 때 출구 방문하면,,
                    if(maps[nr][nc] === 'E' && visitedLever) {
                        return count + 1;
                    }
	                // 위의 둘 외는 그냥 방문처리해주면 된다.
                    visited[nr][nc] = true;
                    q.push([nr, nc, count + 1, visitedLever])
                }
            }

정답코드

function solution(maps) {
    maps = maps.map(v => v.split(''));
    let visited = maps.map(arr => arr.map(v => false));
    
    function bfs(sr, sc){
        let q = [[sr, sc, 0, false]];
        visited[sr][sc] = true;
        while(q.length){
            let [row, col, count, visitedLever] = q.shift();
            const dr = [-1, 1, 0, 0];
            const dc = [0, 0, -1, 1];
            for(let i = 0; i < 4; i++){
                const nr = row + dr[i];
                const nc = col + dc[i];
                if(nr >= 0 && nr < maps.length && nc >= 0 && nc < maps[0].length
                 && !visited[nr][nc] && maps[nr][nc] !== 'X'){
                    // 레버를 처음 방문하는 경우
                    // 방문 배열을 초기화해주고, 방문 flag를 true로, 큐도 초기화
                    if(maps[nr][nc] === 'L' && !visitedLever){
                        visited = maps.map(arr => arr.map(v => false));
                        visited[nr][nc] = true;
                        visitedLever = true;
                        q = [];
                        q.push([nr, nc, count + 1, visitedLever])
                        break;
                    }
                    // 레버통로 방문 flag가 true일 때 출구 방문하면,,
                    if(maps[nr][nc] === 'E' && visitedLever) {
                        return count + 1;
                    }
	                // 위의 둘 외는 그냥 방문처리해주면 된다.
                    visited[nr][nc] = true;
                    q.push([nr, nc, count + 1, visitedLever])
                }
            }
        }
        return -1;
    }
    
    for(let i = 0; i < maps.length; i++){
        for(let j = 0; j < maps[0].length; j++){
            if(maps[i][j] === 'S') return bfs(i,j);
        }
    }
}