[프로그래머스/JavaScript] Lv.2 게임 맵 최단거리

최단거리를 구하는 문제로 너비 우선 탐색(BFS) 문제 유형이다. ( 최단거리는 BFS !!)

BFS 란?
현재 정점에 연결된 가까운 점들부터 탐색하는 방법으로 큐를 이용해서 구현한다.

 

 

function solution(maps) {
    let answer = 1;
    let queue = [];
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    const n = maps.length;
    const m = maps[0].length;
    
    // 시작 위치 담기 
    queue.push([0, 0]);

    // 지나간 위치를 0으로 막는다.(시작 위치도 지나간 위치 이므로 막음)
    maps[0][0] = 0;
    
    // 큐에 담긴 값이 없을 때까지 반복한다.
    while(queue.length > 0) {
        
       /* 
        * queue에 담긴 이동 가능한 좌표가 1개면 1번, 2개면 2번 반복해야 하기 때문에
        * shift 또는 push로 변경되는 queue의 길이를 고정하고 반복한다.
        */
        let size = queue.length;
        for(let i = 0; i < size; i++) {
            let [x, y] = queue.shift();
            
            // 저장된 위치에서 위,아래,좌측,우측 이동 가능 경로 확인하기
            for(let j = 0; j < 4; j++) {
                let nx = x + dx[j];
                let ny = y + dy[j];
                
                /*
                   nx >= 0 &&  ny >= 0 : 맵을 벗어 나지 않기 위한 조건
                   visited[nx][ny] === 1 : 이동할 위치가 막혀있지 않은지 조건
                */
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] === 1) {
                    // 도착 지점 바로 직전
                    if(nx == n-1 && ny == m - 1) {
                        return answer+1;
                    }
                    queue.push([nx, ny]);
                    maps[nx][ny] = 0;
                }
            }
        }
        answer++;
    }
    
    return -1;
}

• 큐에 이동 가능한 위치를 저장하고, 저장된 위치가 없을 때까지 반복한다.
• 지나온 길을 0으로 변경해 1일 경우만 이동하게 한다.
• 큐에 저장된 최근 값( queue.shift )을 가져와 이동 가능 위치(위, 아래, 우측, 좌측)를 확인한다.
• 맵을 벗어나지 않기 위한 조건 (nx >= 0 &&  ny >= 0)을 추가한다.
• 이동 가능하면 큐에 저장하고, 해당 위치를 0으로 변경한다.