[알고리즘/백준/2178] 미로탐색(BFS, 최단거리)

문제

---

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

풀이

---

입력

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m] = N.split(" ").map(Number);
let board = arr.map((row) => row.split("").map(Number));

풀이

function BFS(n, m, board) {
  // BFS
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  let q = [];
  let dis = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

  q.push([0, 0]);
  dis[0][0] = 1;
  board[0][0] = 0;

  while (q.length) {
    const [x, y] = q.shift();

    for (let i = 0; i < dx.length; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx === n - 1 && ny === m - 1) {
        return dis[x][y] + 1;
      }

      if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] === 1) {
        q.push([nx, ny]);
        board[nx][ny] = 0;
        dis[nx][ny] = dis[x][y] + 1;
      }
    }
  }
}

console.log(BFS(n, m, board));

이 문제는 (n, m)에 도착하기 위해 지나야하는 최소 칸의 수, 즉 최단 거리를 구하는 BFS 문제이다.

가장 먼저 출발지점인 (0, 0)을 큐에 넣어준다. 시작 위치도 포함한다고 했으므로 거리 배열 dis[0][0]에 1을 넣어주고 방문 표시를 board[0][0] = 0으로 해준다.

현재 위치 기준으로 4방향을 탐색하면서 이동 가능한 지점인 경우에는 큐에 넣는다. 만약 도착지점에 왔다면(if (nx === n-1 && ny === m-1)) 이전 위치까지의 최단 거리(dis[x][y])에 +1을 해서 답을 구한다.