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

8741 단어 Level 2Level 2

문제

게임 맵 최단거리 https://programmers.co.kr/learn/courses/30/lessons/1844

해결

목적지까지 최단거리를 구하는 문제이기 때문에 BFS를 이용하여 구현했습니다.
남서북동 순으로 dy, dx를 구현한 후, 0 ~ 4 까지의 index를 이용하여 이동할 수 있는지 체크 후, 이전 칸 +1을 하면서 현재 위치의 최단 거리를 계산합니다.
초기 세팅을 1로 했는데 목적지의 count가 1이라면 도달할 수 없다는 뜻 입니다.

코드

function solution(maps) {
  // 남서북동 순서
  const dy = [1, 0, -1, 0];
  const dx = [0, -1, 0, 1];
  const row = maps.length; // 행
  const col = maps[0].length; // 열
  const visitCount = [...maps].map((r) => r.map((c) => 1));

  let temp = 0;
  const queue = [[0, 0]];
  while (queue.length) {
    const [y, x] = queue.shift();

    for (let k = 0; k < 4; k++) {
      const ny = y + dy[k];
      const nx = x + dx[k];

      if (ny >= 0 && nx >= 0 && ny < row && nx < col) {
        if (maps[ny][nx] === 1 && visitCount[ny][nx] === 1) {
          visitCount[ny][nx] = visitCount[y][x] + 1;
          queue.push([ny, nx]);
        }
      }
    }
  }

  return visitCount[row - 1][col - 1] === 1 ? -1 : visitCount[row - 1][col - 1];
}

좋은 웹페이지 즐겨찾기