[boj] 2178. 미로 탐색 (node.js)

요약

BOJ 2178 미로탐색

• 입력: N * M 크기의 미로가 주어진다.
• 출력: (1,1) 에서 (N, M)까지의 최단거리를 구하라.
• 주어진 미로에서 0은 이동할 수 없는 영역으로, 1이 적힌 칸으로만 이동 가능하다.

풀이

• 입력된 미로를 인접 행렬 형태로 변환한다. BFS 탐색을 이용해 최단거리를 갱신하는 방식으로 답을 구할 수 있다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let cnt = 0;
const input = () => stdin[cnt++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const [N, M] = input().split(" ").map(Number);
  const arr = new Array(N);
  let visited = new Array(N);
  let dist = new Array(N);
  let queue = [];
  const dir = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];

  for (let i = 0; i < N; i++) {
    arr[i] = input();
    visited[i] = new Array(M).fill(0);
    dist[i] = new Array(M).fill(10000);
  }
  console.log(bfs(0, 0));
  process.exit();

  function bfs(x, y) {
    queue.push([x, y]);
    visited[x][y] = 1;
    dist[x][y] = 1;
    while (queue.length > 0) {
      [qx, qy] = queue.shift();
      for (let i = 0; i < 4; i++) {
        nx = qx + dir[i][0];
        ny = qy + dir[i][1];
        if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
        if (arr[nx][ny] == "1" && !visited[nx][ny]) {
          queue.push([nx, ny]);
          visited[nx][ny] = 1;
          dist[nx][ny] = Math.min(dist[qx][qy] + 1, dist[nx][ny]);
        }
        if (nx == N - 1 && ny == M - 1) return dist[nx][ny];
      }
    }
  }
});

• 문제 풀이를 위해 최단 거리를 저장하는 배열은 만든다.
• N, M의 범위가 2와 100 사이이므로 입력값 갱신 dist[nx][ny] = Math.min(dist[qx][qy] + 1, dist[nx][ny]);을 위해 dist 배열 원소의 초기값은 10000으로 설정한다.