프로그래머스: 게임 맵 최단거리 (BFS)

게임 맵 최단거리

n * m 크기의 맵을 표현하는 이중 배열 maps가 주어질 때, 첫 번째 배열의 첫 번째 인덱스에서 출발하는 캐릭터가 목적지까지 도달하기 위한 최단거리를 구하기

제한 조건
1 ≤ n ≤ $10^2$
1 ≤ m ≤ $10^2$

문제 풀이 조건
n, m은 같은 값일 수 있으나, 둘 다 1인 경우는 없다. maps는 0과 1만 요소로 갖는 이중 배열이며 0은 벽, 1은 길을 나타낸다.
캐릭터는 길로만 이동할 수 있다.
목적지는 반드시 좌표상 (n, m)이며, 출발지는 (1, 1)이다.

알고리즘 구상하기

시간복잡도를 줄이는데 집중한다.
문제를 풀기 위해서는 n * m 이중 배열을 순회하며 길(1) 요소만 방문하며 목적지에 접근해야 한다.

이는 가지치기 형태의 그래프로 나타낼 수 있으며 그래프를 탐색하여 최단거리로 목적지에 도달하는 경우를 구할 수 있다.

적절한 자료구조: BFS
그래프를 탐색하는 알고리즘에는 크게 DFS와 BFS가 있다. 이번 문제는 길을 나타내는 요소 1만 방문하기 때문에 특정 index의 요소에 접근할 수 있는 방법이 한정되어 있다는 특징이 있다.

최단거리를 구하는데 있어, 같은 요소를 두 번 방문하는 방법은 비효율적이며 유사한 루트(route)를 목적지에 도달하기 전까지 계속 반복하는 것도 효율적으로 떨어진다고 판단했다.

이에 따라 깊이 우선 탐색으로 목적지에 도달하기 전까지 탐색을 수행하는 DFS 보다는, 인접한 요소부터 방문하며 route를 늘려가는 BFS가 상대적으로 효율적이라 판단하여 BFS를 채택하였다.

효율적인 큐(queue)관리로 시간복잡도를 저감한다.
이번 BFS 알고리즘은 shift 메서드로 인해 효율성 테스트를 통과하지 못했던 전적들을 참작하여, queue를 순회하는 방식으로 바로 구현했다.

[JavaScript]

function solution(maps) {
  const n = maps[0].length;
  const m = maps.length;
  const visited = maps.map((coordinate) => [...coordinate]);
  visited[0][0] = 0;
  let queue = [[0, 0, 1]];
  const move = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];

  while (queue.length > 0) {
    const newQueue = [];

    for (let i = 0; i <= queue.length - 1; i++) {
      const coordinate = queue[i];
      const [y, x, count] = coordinate;

      for (let j = 0; j <= move.length - 1; j++) {
        const movedY = y + move[j][0];
        const movedX = x + move[j][1];

        if (
          movedY === m - 1 &&
          movedX === n - 1 &&
          visited[m - 1][n - 1] === 1
        ) {
          return count + 1;
        }

        if (
          movedY >= 0 &&
          movedY <= m - 1 &&
          movedX >= 0 &&
          movedX <= n - 1 &&
          visited[movedY][movedX] === 1
        ) {
          visited[movedY][movedX] = 0;
          newQueue.push([movedY, movedX, count + 1]);
        }
      }
    }

    queue = newQueue.map((coordinates) => [...coordinates]);
  }

  return -1;
}

Comment

이중 배열은 spread 연산자로 깊은 복사를 수행할 수 없다.

spread 연산자는 depth 1인 배열만 깊은 복사를 수행하고 depth 2인 배열들은 얕은 복사가 된다.
이에 따라, map 메서드를 이용하여 각 요소들에 직접 깊은 복사를 적용하는 방법으로 이중 배열 maps를 복사하였다.

const visitedSpread = [...maps]; // 의도대로 작동하지 않음.
const visitedMap = maps.map((coordinate) => [...coordinate]); // 이중 배열 깊은 복사