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

문제

코딩테스트 연습 - 게임 맵 최단거리

 

풀이

 

n x m 행렬에서 (1,1)에서 시작해서 (n,m)에 도달하는 최단경로를 출력한다.

(n,m)에 도달할 수 없다면 -1을 출력한다.

 

풀이 방법

최단경로를 구해야 하므로 BFS 유형의 문제이다.

 

현재 위치에서, 상하좌우 이동 가능 여부를 판단한다.

상하좌우가 벽(0)이거나, 행렬의 범위를 벗어났다면 이동할 수 없다.
이동할 수 있다면 이동할 좌표와 이동한 횟수를 큐에 넣는다.

 

FIFO를 따라 BFS 함수의 Queue에서 좌표 (x,y)가 (n, m)와 같다면 바로 BFS 함수를 종료하고 최단경로를 출력한다.
Queue에 원소가 존재하지 않을 때 까지 (x,y)가 (n, m)에 도달하지 못했다면 -1을 출력한다.

 

코드

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

  let answer = -1;
  function bfs(sx, sy, scnt) {
    const queue = [];
    queue.push([sx, sy, scnt]);
    maps[sx][sy] = 0;
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    
    while (queue.length) {
      const [x, y, cnt] = queue.shift();
      if (x === n && y === m) {
        answer = cnt;
        return;
      }
      for (let i = 0; i < 4; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx > n || ny > m) continue;
        if (maps[nx][ny] === 1) {
          maps[nx][ny] = 0;
          queue.push([nx, ny, cnt + 1]);
        }
      }
    }
    return;
  }

  bfs(0, 0, 1);
  return answer;
}