programmers. 게임 맵 최단거리

문제

문제

풀이

처음에 dfs로 구현해서 자꾸 헛짓하다가 안 풀려서 찾아보고 bfs로 풀었다

사실 bfs를 구현해서 푼 적이 한 번도 없어서 어떤 때 적용해야하는지 조차 몰랐었기 때문에

응용 방법을 배워 간 문제

코드

function solution(maps) {
    let answer = -1;
    const moveTo = [
        {x:0,y:1},
        {x:0,y:-1},
        {x:1,y:0},
        {x:-1,y:0}
    ]
    // 이동할 위치가 들어가있는 큐, [0,0]에서 시작하기 때문에 0,0을 입력
    const queue = [[0,0,1]];

    while (queue.length){
        // 이동할 위치를 큐 빼내 현재 위치로 지정
        const [MyY, MyX, cnt] = queue.shift();

        // 목적지에 도착했다면 answer에 이동 거리를 넣고 종료
        if(MyY=== maps.length-1 && MyX===maps[0].length-1){
            answer = cnt;
            break;
        }

        // 상하좌우로 이동하기위해 반복문을 돌림
        for(let i=0; i<4;i++){
            const {x, y} = moveTo[i];
            const moveToX = MyX+x;
            const moveToY = MyY+y;

            // 범위를 벗어난 경우 이동하지 않음
            if(moveToX<0 || moveToY<0 || moveToX>maps[0].length|| moveToY>maps.length-1){
                continue;
            }
            // 이미 방문했거나 벽인 경우 이동하지 않음
            if(maps[moveToY][moveToX] ===2 || maps[moveToY][moveToX]===0){
                continue;
            }
            // 위 조건들을 만족하면 이동할 위치에 방문함을 표시
            maps[moveToY][moveToX] = 2;
            // 이동 할 위치에 추가
            queue.push([moveToY, moveToX, cnt+1]);
        }
    }
    return answer;
}