[JavaScript/알고리즘] 게임 맵 최단거리 (BFS)

프로그래머스 Lv 2 - 게임 맵 최단거리

Solved-Algorithm/JavaScript/프로그래머스/2/1844. 게임 맵 최단거리 at main · ParkBible/Solved-Algorithm

 

상하좌우로 움직일 수 있는 전형적인 BFS 문제입니다.

function solution(maps) {
    const n = maps.length;
    const m = maps[0].length;
    const dist = Array.from(Array(n), () => new Array(m).fill(1));
    const queue = [[0, 0]];

    while (queue.length > 0) {
        const position = queue.shift();
        const now = {y: position[0], x: position[1]};

        if (now.y === n - 1 && now.x === m - 1) {
            return dist[now.y][now.x];
        }

        const nextPositions = [
            [now.y - 1, now.x], [now.y + 1, now.x], [now.y, now.x + 1], [now.y, now.x - 1]
        ];

        nextPositions.forEach(coord => {
            const next = {y: coord[0], x: coord[1]};

            if (next.y >= 0 && next.x >= 0 && next.y < n && next.x < m) {
                if (maps[next.y][next.x] === 1) {
                    queue.push([next.y, next.x]);
                    maps[next.y][next.x] = 0;
                    dist[next.y][next.x] = dist[now.y][now.x] + 1;
                }
            }
        });
    }

    return -1;
}

 

헤맸던 부분

• x, y 좌표를 반대로 적음. 이차원 배열 문제에서 배열은 [y][x] 형태이다.
• 밖으로 벗어나는 경우에 대해 제대로 검증하지 못함. 다음 좌표가 0보다 같거나 커야 한다는 조건은 입력했지만 n, m보다 작아야 한다는 조건을 적지 않음.
• 9번째 라인은 const [nowY, nowX] = position; 으로도 표현할 수 있다.
• 이차원 배열을 초기화 하는 방법은 Array.from(Array(Y축길이), () => new Array(X축길이)); 이다. 형태는 Array.from(배열 혹은 유사 배열, 적용할 함수);
• 이차원 배열을 아래와 같이 for of 문으로 돌릴 수 있다.

const directions = [
    [0, -1], [-1, 0], [1, 0], [0, -1]
];

for (const [dy, dx] of directions) {
    console.log(dy, dx);
}