[프로그래머스] 게임 맵 최단거리 (JS)

풀이 과정

1. 맵과 크기가 같은 visited 배열 생성
2. 큐에 값을 넣으면서 BFS
   이때 visited에 이동한 거리를 같이 기록
3. 상대팀 진영에 도달하면 거리 리턴
   도달할 수 없는 경우 -1 리턴

코드

// 오른 아래 왼 위
const dy = [0, 1, 0, -1];
const dx = [1, 0, -1, 0];

function solution(maps) {
  const [n, m] = [maps.length, maps[0].length];
  const visited = Array(n)
    .fill(null)
    .map((_) => Array(m).fill(0));
  const q = [[0, 0]];
  visited[0][0] = 1;
  while (q.length) {
    const [y, x] = q.shift();
    if (y === n - 1 && x === m - 1) return visited[y][x];
    for (let i = 0; i < 4; ++i) {
      const [ny, nx] = [y + dy[i], x + dx[i]];
      if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
      if (!maps[ny][nx] || visited[ny][nx]) continue;
      visited[ny][nx] = visited[y][x] + 1;
      q.push([ny, nx]);
    }
  }
  return -1;
}

🤔

아직 몰라도 너무 모른다. 최단 거리 구하는 문제는 처음인데, BFS 알고리즘 자체가 최단 거리를 구하는 거라 여러 경로로 도달할 경우를 고려할 필요가 없다고 한다.

• 각 칸에 단순 visited 표시가 아니라 움직인 거리를 기록해야 이전 칸을 바탕으로 이동 거리를 계산해서 정확히 이동한 거리를 알 수 있음