백준 2178 미로 탐색

문제

1,1부터 출발해서 마지막 칸까지 가는데 필요한 최소 칸 수를 구하는 문제이다. 전형적인 그래프 탐색 문제이다. dfs로 풀게 되면 자기가 들어갈 수 있는 만큼 계속 안쪽으로 먼저 파고들면서 탐색하는게 선행되기 때문에 최소거리는 구하기 힘들다. 그러므로 bfs로 탐색하는게 더 효과적이다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [f, ...maps] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [n, m] = f.split(" ").map(Number);
const maze = maps.map((m) => Array.from(m));
const visited = Array.from({ length: n }, () => new Array(m).fill(false));
const dLoc = [
  [-1, 0],
  [1, 0],
  [0, 1],
  [0, -1],
];
 
function bfs() {
  const queue = [[0, 0, 1]];
  while (queue.length) {
    const [x, y, cnt] = queue.shift();
    if (x === n - 1 && y === m - 1) {
      console.log(cnt);
      return;
    }
    visited[x][y] = true;
 
    for (const [dx, dy] of dLoc) {
      const nx = x + dx;
      const ny = y + dy;
      if (
        nx >= 0 &&
        nx < n &&
        ny >= 0 &&
        ny < m &&
        !visited[nx][ny] &&
        maze[nx][ny] === "1"
      ) {
        queue.push([nx, ny, cnt + 1]);
      }
    }
  }
}
 
bfs();

처음에는 이렇게 했었다. 하지만 이상하게도 시간 초과가 났다. 방문 처리도 잘 했고, 큐에 배열을 넣는 것까지 문제 없다고 생각했다. 하지만 여기에서 문제는 방문처리에 있었다. while문을 돌면서 queue에서 빼낼 때 방문 처리를 하게 되면 dLoc을 돌면서 새로운 경로를 추가할 때는 visited 배열이 갱신되기 전이기 때문에 방문할 예정인 노드 또한 다시 추가되는 문제가 생긴다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [f, ...maps] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const [n, m] = f.split(" ").map(Number);
const maze = maps.map((m) => Array.from(m));
const visited = Array.from({ length: n }, () => new Array(m).fill(false));
const dLoc = [
  [-1, 0],
  [1, 0],
  [0, 1],
  [0, -1],
];
 
function bfs() {
  const queue = [[0, 0, 1]];
  visited[0][0] = true;
 
  while (queue.length) {
    const [x, y, cnt] = queue.shift();
    if (x === n - 1 && y === m - 1) {
      console.log(cnt);
      return;
    }
 
    for (const [dx, dy] of dLoc) {
      const nx = x + dx;
      const ny = y + dy;
      if (
        nx >= 0 &&
        nx < n &&
        ny >= 0 &&
        ny < m &&
        !visited[nx][ny] &&
        maze[nx][ny] === "1"
      ) {
        visited[nx][ny] = true;
        queue.push([nx, ny, cnt + 1]);
      }
    }
  }
}
 
bfs();

이를 해결하기 위해서 새로운 경로를 추가할 때 미리 visited 배열을 갱신해주었다.

경로의 방문 처리는 항상 신경 써서 풀자 !