[백준] 2178. 미로 탐색 (자바스크립트/js/javascript/node.js/BFS/최단경로)

모든 노드를 탐색한다면 DFS와 BFS 모두 상관없겠지만 주어진 문제는 두 지점간의 최단경로를 탐색해야 하기 때문에 BFS를 사용하는 문제이다. BFS는 가중치가 없는 간선간의 최단거리를 보장할 수 있다. 

 

BFS가 최단거리를 보장하는 이유는 다음과 같다.

BFS는 자신과 바로 연결되어 있는 노드들을 큐에 넣는다. 그리고 큐는 FIFO에 따라서 가장 먼저 들어온 것들을 먼저 처리한다. 이 두가지 특성이 결합되어 시작지점으로부터 간선의 수가 작은 곳부터 먼저 처리되게 된다. 따라서 간선 2개로 도달할 수 있는 노드가 간선 1개로 도달할 수 있는 노드보다 큐에 먼저 들어오는 일은 발생하지 않으므로 최단거리를 보장할 수 있다.

 

주어진 문제는 1,1에서 시작하여 N,M까지의 최소 칸 수를 구해야 하는데, 즉 (1,1)에서 (N,M)까지의 최단경로를 구하는 것이다. 

 

방문여부를 확인할 수 있는 visited 배열을 만들어서 NxM 사이즈로 0으로 가득 채운다.

또한 경로를 확인할 수 있는 path 배열을 만들어서 NxM 사이즈로 0으로 가득 채운다.

 

나머지는 기존의 BFS 방법으로 그냥 푸는데, 이 때 지나온 칸의 수를 체크해주어야 하기 때문에 path에 값을 넣어준다.

맨 처음에는 path[r][c]에 1을 넣고 (시작 위치도 포함해야 하므로) 그 다음에 인접한 노드들 중에서 1) 동서남북으로 이동할 수 있으며(범위체크) 2) 방문한 적이 없고 3) 이동할 수 있는 경로인지 확인하고,  모든 조건에 부합하다면 이 때 path[nextRow][nextCol]의 값은 path[currentRow][currentcol]보다 1을 더하여 넣어준다. 

이렇게 하고 path를 최종적으로 출력해보면 예제 1의 경우 

 

1  0  9  10  11 12
2  0  8   0   12   0
3  0  7   0   13 14
4  5  6   0   14 15

 

이렇게 나오는 것을 확인할 수 있다. 저 숫자 순서대로 가다가 (N,M)에 도착하는 것이다.

let fs = require("fs");
let graph = fs.readFileSync("/dev/stdin").toString().split("\n");
const N = Number(graph[0].split(" ")[0]); // 행
const M = Number(graph[0].split(" ")[1]); // 열
graph.shift();
graph = graph.map((element) => element.trim().split(""));
const visited = Array.from(new Array(N), () => new Array(M).fill(0));
const path = Array.from(new Array(N), () => new Array(M).fill(0));

const moveRow = [0, 0, 1, -1];
const moveCol = [1, -1, 0, 0];
const rangeCheck = (row, col) => {
  if (row >= 0 && row < N && col >= 0 && col < M) {
    return true;
  }
  return false;
};
const BFS = (r, c) => {
  const queue = [];
  queue.push([r, c]);
  path[r][c] = 1;

  while (queue.length) {
    const target = queue.shift();
    currentRow = target[0];
    currentCol = target[1];

    if (!visited[currentRow][currentCol]) {
      visited[currentRow][currentCol] = 1; // 방문처리

      for (let n = 0; n < 4; n++) {
        const nextRow = currentRow + moveRow[n];
        const nextCol = currentCol + moveCol[n];
        if (
          rangeCheck(nextRow, nextCol) &&
          Number(graph[nextRow][nextCol]) === 1 &&
          !visited[nextRow][nextCol]
        ) {
          queue.push([nextRow, nextCol]);
          path[nextRow][nextCol] = path[currentRow][currentCol] + 1;
        }
      }
    }
  }
};

BFS(0, 0);
console.log(path[N - 1][M - 1]);