[프로그래머스] Lv. 2 게임 맵 최단거리

문제

문제 링크

설명

BFS로 풀었다.

공간 절약을 위해 visited 배열을 따로 만들지 않았다.

 

시작 좌표의 값을 2로 둔다.

다음 칸을 탐색할 때 이전 칸의 값에 1을 더한 값을 저장한다.

도착 지점의 값에 1을 빼준 값이 답이다.

while문이 끝날 때 까지 return되지 않았으면 도착할 수 없는 경우이므로, -1을 return한다.

아래는 bfs를 돌렸을 때 maps 배열의 예시이다.

[
  [ 2, 0, 10, 11, 12 ],
  [ 3, 0, 9, 0, 11 ],
  [ 4, 0, 8, 9, 10 ],
  [ 5, 6, 7, 0, 11 ],
  [ 0, 0, 0, 0, 12 ]
]

코드

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