문제 링크

바로가기

문제 풀이

function solution(maps) {
    const m = maps.length;
    const n = maps[0].length;
    const dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    
    const bfs = () => {
        const queue = [];
        queue.push([0, 0, 1]);
        maps[0][0] = 0;
        
        while(queue.length > 0) {
            const [row, col, distance] = queue.shift();
            
            if(row === m - 1 && col === n - 1) {
                return distance;
            }
            
            for(let i = 0; i < dir.length; ++i) {
                const [x, y] = dir[i];
                const newRow = row + x;
                const newCol = col + y;
                
                if(newRow < 0 || newCol < 0 || newRow >= m || newCol >= n || maps[newRow][newCol] === 0) continue;
                
                queue.push([newRow, newCol, distance + 1]);
                maps[newRow][newCol] = 0;
            }
        }
        
        return -1;
    }
    
    return bfs();
}

새롭게 배운 점

너비 우선 탐색의 전형적인 문제인 길찾기를 풀어보았다.
JS로 BFS 문제를 푸는게 처음이라 조금 헤맸지만 그래도 길찾기 문제는 정해진 양식이 있는 것 같다.

1. 방향 만들기
2. 시작점 넣고 while문으로 큐가 비어있을 때까지 돌리기
3. while문 넣자마자 원소 빼고 목표 설정하기
4. 방향 만큼 반복문으로 돌리면서 큐에 방향 넣어주기
5. 방향 넣어주면 다녀온 처리하기

이렇게 외워두자!