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

문제 링크

프로그래머스

 

문제 유형

DFS/ BFS

 

문제 풀이

 

해당 문제는 상대 팀 진영에 도착하기 위해 지나가야 하는 칸의 최소 개수 즉, 최단 거리를 구하는 문제이다. 최단 거리를 구할 때는 DFS 보다 BFS가 유리하다. DFS는 도착점으로 가기 위한 모든 경로를 탐색해야 하지만 BFS는 타겟에 도착한 순간 종료할 수 있기 때문이다.

큐에는 출발점과 칸의 최소 개수를 넣는다. 큐에서 요소를 하나씩 꺼내고 현재 지점이 상대 팀 진영인 매트릭스의 가장 오른쪽 아래라면 칸의 개수를 리턴한다. 그렇지 않으면 현재 지점의 아래, 오른쪽, 위, 왼쪽으로 한칸 새로 이동한 지점을 확인한다. 새로 이동한 지점이 게임 맵을 벗어난 곳이거나 벽인 경우 큐에 넣지 않는다. 새로 이동한 지점이 갈 수 있는 곳이라면 해당 지점을 다시 지나갈 수 없도록 벽으로 만들고, 큐에 넣는다.

 

코드

function solution(maps) {
    const directions = [[1, 0], [0, 1], [-1, 0], [0, -1]];
    const n = maps.length - 1, m = maps[0].length - 1;
    
    const queue = [[0, 0, 1]];
    
    while (queue.length) {
        const [r, l, count] = queue.shift();
        if (r === n && l === m) return count;
        
        for (let direction of directions) {
            const nr = r + direction[0], nl = l + direction[1];
            // 게임 맵을 벗어난 경우
            if (nr < 0 || nr > n || nl < 0 || nl > m) continue;
            // 벽인 경우
            if (!maps[nr][nl]) continue;
            maps[nr][nl] = 0; // 이미 지나간 길을 지나갈 수 없도록 벽으로 만듬
            queue.push([nr, nl, count + 1]);
        }
    }
    return -1;
}