문제 개요

문제: 알고스팟

분류: 그래프 이론, 그래프 탐색, 데이크스트라, 최단 경로, 0-1 너비 우선 탐색

난이도: 골드4

문제 풀이

다른 사람 풀이를 참고했다.

BFS를 사용하되 벽을 최소로 부숴야 하므로 최대한 벽이 없는 곳부터 방문한다.

• 다음 위치가 빈 방이라면 unshift()를 통해 queue의 앞에 추가하여 먼저 꺼내서 탐색하도록 한다.
• 다음 위치가 벽이라면 push()를 통해 queue의 뒤에 추가하여 빈 방인 곳보다 나중에 탐색하도록 한다.

(N, M)에 도착했을 때 현재까지 부순 벽의 개수를 출력하고 프로그램을 종료한다.

코드

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

const solution = (M, N, miro) => {
  const [dy, dx] = [
    [-1, 1, 0, 0],
    [0, 0, -1, 1],
  ];

  const bfs = () => {
    const queue = [];
    const visited = Array.from(Array(N), () => Array(M).fill(false));

    queue.push([0, 0, 0]);
    visited[0][0] = true;

    while (queue.length > 0) {
      const [y, x, wall] = queue.shift();
      if (y === N - 1 && x === M - 1) return wall;

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

        if (ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx]) continue;
        visited[ny][nx] = true;

        // 벽을 부수지 않는 것을 우선시하기 위해 빈 방의 경우 큐의 앞쪽에, 벽의 경우 큐의 뒤쪽에 추가한다.
        if (miro[ny][nx] === "0") queue.unshift([ny, nx, wall]);
        else queue.push([ny, nx, wall + 1]);
      }
    }
  };

  console.log(bfs());
};

solution(M, N, miro);