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

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

프로그래머스

문제 설명

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

 

 

문제 해결 아이디어

기본적인 그래프 탐색 문제이다. 효율성을 체크하는 부분이 있어서 DFS가 아닌 BFS로 풀었다.

자바로 알고리즘 문제 풀 때와 똑같은 방법으로 푸는데 늘 2차원 배열 만들 때 Array.fill로 하면 얕은 복사가 된다는 걸 까먹어서 다시 한번 제대로 정리해 둔다.

fill은 얕은 복사로 값을 채우기 때문에 채워진 빈 배열들은 같은 주소를 띄고 있다. 따라서 배열의 값을 바꾸면 동일한 행의 값이 다 바뀌게 된다.

Array.from(Array(row), () => Array(column).fill(false));

앞으로는 이런 식으로 선언해 주자!

 

 

완성된 코드

function solution(maps) {
    var answer = Number.MAX_VALUE;

    let queue = [];
    let isVisited = Array.from(Array(maps.length), () =>
        Array(maps[0].length).fill(false)
    );

    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    queue.push([0, 0, 1]);
    let now = [];
    let r = 0,
        c = 0,
        nr = 0,
        nc = 0,
        cnt = 1;

    while (queue.length > 0) {
        now = queue.shift();
        r = now[0];
        c = now[1];
        cnt = now[2];

        if (r === maps.length - 1 && c === maps[0].length - 1) {
            answer = Math.min(answer, cnt);
        }

        for (let i = 0; i < 4; i++) {
            nr = r + dr[i];
            nc = c + dc[i];

            if (
                nr >= 0 &&
                nr < maps.length &&
                nc >= 0 &&
                nc < maps[0].length &&
                maps[nr][nc] !== 0 &&
                isVisited[nr][nc] === false
            ) {
                isVisited[nr][nc] = true;
                queue.push([nr, nc, cnt + 1]);
            }
        }
    }
    return answer === Number.MAX_VALUE ? -1 : answer;
}