1844. 게임 맵 최단거리

프로그래머스 1844번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨

풀이

아이디어

최단 경로를 찾는 전형적인 BFS 문제이다.

• 시작점에서 가까운 곳부터 순서대로 탐색하기 때문에 처음 상대 진영에 도달했을 때의 거리가 최단경로이다.
• DFS는 비슷하지만 모든 경로를 탐색해야 하기 때문에(상대 진영에 도달한 이후에도 계속 탐색해야 함) 비효율적이다.

DFS 구현 포인트

1. shift는 O(N) 시간복잡도를 갖기 때문에 frontIdx를 활용해서 O(1)로 동작하는 dequeue를 구현했다.
2. 시작점을 큐에 넣을 때 방문 처리를 잊지 말자.
3. 가중치가 없으므로 처음으로 상대 진영에 도착했을때의 경로 길이가 최단 경로이다. 그래서 따로 Math.min으로 최소 경로 길이를 비교할 필요 없다.

코드

function solution(maps) {
  const queue = [];
  let frontIdx = 0;
  const rows = maps.length;
  const cols = maps[0].length;
  const visited = Array.from({ length: rows }, () =>
    new Array(cols).fill(false)
  );
  const dx = [1, 0, -1, 0];
  const dy = [0, 1, 0, -1];
  const dequeue = () => {
    const ret = queue[frontIdx];
    frontIdx++;
    return ret;
  };

  const goal = { x: cols - 1, y: rows - 1 };
  const player = { x: 0, y: 0, length: 1 };
  queue.push({ ...player });
  visited[0][0] = true;
  while (frontIdx < queue.length) {
    const front = dequeue();
    // 상대 진영 도착 확인
    if (front.x === goal.x && front.y === goal.y) {
      return front.length;
    }
    for (let di = 0; di < 4; di++) {
      const nx = front.x + dx[di];
      const ny = front.y + dy[di];
      const nl = front.length + 1;

      if (
        nx < 0 ||
        nx >= cols ||
        ny < 0 ||
        ny >= rows || // 범위 확인
        maps[ny][nx] === 0 || // 길 확인
        visited[ny][nx] // 방문 확인
      ) {
        continue;
      }

      visited[ny][nx] = true;
      queue.push({ x: nx, y: ny, length: nl });
    }
  }
  return -1;
}