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

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

풀이

function solution(maps) {
    const xLength = maps.length;
    const yLength = maps[0].length;
    const dx = [0, 0, -1, 1];
    const dy = [-1, 1, 0, 0];
    
    const bfs = () => {
        const queue = [[0, 0, 1]];
        while (queue.length) {
            const [x, y, count] = queue.shift();
            if (x === xLength - 1 && y === yLength - 1) {
                return count;
            }
            if (maps[x][y]) {
                maps[x][y] = 0;
                dx.forEach((dx, i) => {
                    const nx = x + dx;
                    const ny = y + dy[i];
                    if (nx >= 0 && nx < xLength && ny >= 0 && ny < yLength && maps[nx][ny]) {
                        queue.push([nx, ny, count + 1]);
                    }
                });
            }
        }
        return -1;
    };
    return bfs();
}

 

너비 우선 탐색을 통해 상대 팀 진영으로 가는 최단 거리를 구할 수 있다.

 

큐에 [x좌표, y좌표, 움직인 칸 수]를 push하는 방식으로 해당 좌표까지 오는데 움직인 최소 칸 수를 얻어낼 수 있다.

벽이 아닌 칸만 갈 수 있으므로 if문 조건에 maps[nx][ny]를 넣어 0이 아닌 경우에만 큐에 push하도록 하였다.

 

최종적으로 x, y좌표가 상대 팀 진영과 같을 때 그 때 count(움직인 칸 수)가 상대 팀 진영으로 가는 최단거리이다.

만약 while문을 그냥 빠져나왔다면 모든 이동 가능한 칸을 다 방문했음에도 상대 팀 진영에 도달하지 못한 것이므로, -1을 반환하도록 하였다.

 

처음에는 visited 배열을 만들어서 방문 여부를 2차원 배열에 boolean을 담아서 표시하였으나, 효율성 테스트 3에서 시간 초과가 났다. 그래서 visited 배열을 따로 만들지 않고, 원본 maps의 칸을 1에서 0으로 변경시키는 방법으로 하였더니 통과하였다.