[Javascript/자바스크립트] 프로그래머스 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=javascript

코드

function solution(maps) {
  const n = maps.length;
  const m = maps[0].length;

  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];

  const visited = Array.from(new Array(n), () => new Array(m).fill(false));
  visited[0][0] = true;
  const q = [];
  q.push({ x: 0, y: 0, cnt: 1 });
  while (q.length > 0) {
    const { x, y, cnt } = q.shift();
    if (x === n - 1 && y === m - 1) {
      return cnt;
    }
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (
        nx >= 0 &&
        nx < n &&
        0 <= ny &&
        ny < m &&
        maps[nx][ny] === 1 &&
        !visited[nx][ny]
      ) {
        visited[nx][ny] = true;
        q.push({ x: nx, y: ny, cnt: cnt + 1 });
      }
    }
  }
  return -1;
}

 

 

풀이

BFS 수행

큐가 빌 때까지 반복하며 BFS를 수행한다.

• 큐에서 현재 위치(x, y)와 이동 횟수(cnt)를 꺼낸다.
• 현재 위치가 목표점(n-1, m-1)이면 이동 횟수(cnt)를 리턴한다.
• 만약 리턴하지 않았다면 현재 위치에서 상하좌우 4방향으로 이동할 수 있는지 확인한다. 이동 가능한 조건은:
  • 맵 범위 내에 있는지 (0 <= nx < n && 0 <= ny < m)
  • 해당 이 벽이 아닌지 (maps[nx][ny] === 1)
  • 아직 방문하지 않은 칸인지 (!visited[nx][ny])
• 조건을 만족하면 해당 칸을 방문 처리하고 큐에 새 칸을 추가한다.

만약 큐가 빌 때까지 목표점에 도달하지 못했다면 -1을 반환한다.

 

---

자바스크립트의 BFS는 파이썬과 뭐가 다를까 했는데, 별 다른 것이 없었다....

다만 DFS에서 스택을 사용하여 구현하는 방법을 찾았으니 그걸 연습해봐야 겠다.