[PRO] 프로그래머스 Lv.2 게임 맵 최단 거리 (Javascript)

문제

프로그래머스

 

 

문제 해석

접근 방법

2차원 배열로 주어진 게임 맵에서 1, 1에서 n, m까지 도착할 수 있는 최단 거리를 구하는 문제입니다.

최단 경로 문제의 경우 경로를 찾는 즉시 탐색을 종료할 수 있는 BFS로 구현할 수 있습니다.

 

풀이 과정

문제에서 요구한 1, 1과 n, m을 편의상 0, 0과 n-1, m-1로 바꾸어 풀이했습니다.

 

bfs 함수를 사용해 인접 칸에 이동합니다.

방문 시에는 현재까지 이동한 거리 +1을 2차원 visited 배열에 저장합니다.

 

만약 탐색 중에 목적지에 도착할 시에는 이동한 거리를 반환합니다.

그렇지 않고 모든 좌표를 탐색할 때까지(queue에 남아있는 좌표가 없을 때까지) 도착하지 못하면 -1을 반환합니다.

 

전체 코드

function solution(maps) {
    const n = maps.length,
        m = maps[0].length;
    const bfs = () => {
        const queue = [[0, 0]];
        const [dx, dy] = [
            [0, 0, 1, -1],
            [1, -1, 0, 0],
        ];
        const visited = Array(n)
            .fill()
            .map((m) => Array(m).fill(0));
        visited[0][0] = 1;

        while (queue.length) {
            const [x, y] = queue.shift();

            if (x === n - 1 && y === m - 1) return visited[x][y];

            for (let i = 0; i < 4; i++) {
                const [nx, ny] = [x + dx[i], y + dy[i]];
                if (
                    0 <= nx &&
                    nx < n &&
                    0 <= ny &&
                    ny < m &&
                    maps[nx][ny] &&
                    !visited[nx][ny]
                ) {
                    visited[nx][ny] = visited[x][y] + 1;
                    queue.push([nx, ny]);
                }
            }
        }
        return -1;
    };

    return bfs();
}