[백준] 1261번 알고스팟 - JavaScript(NodeJS)

문제

1261번: 알고스팟

 

풀이

N x M 크기 미로에서 (1,1)에서 시작하여 (N,M)에 도달하면 끝난다.

 

미로에서는 벽이 없다면 바로 이동하며, 벽이 있다면 부수고 이동할 수 있다.
(N,M)에 도달하기까지 벽을 최소 몇 개 부수고 이동할 수 있는지를 구하면 된다.

이동은 상하좌우로 총 4방향이 가능하다.

 

풀이 방향

13549 숨바꼭질3 문제와 유사한데, 작업의 우선순위를 설정해야 한다.

 

즉, 목적지에 도착하기까지 벽을 최대한 부수지 말아야 하므로, 벽을 부수지 않는 이동에 우선순위를 준다.

 

BFS를 사용하는 것은 같다.

Deque 자료구조를 사용해서, 매 스텝마다 벽을 부수지 않는 이동을 우선적으로 처리한다.

 

벽을 부수지 않는 이동이 우선적으로 처리되므로

미로의 크기만큼 방문 배열을 추가로 선언해서, 동일한 위치로 이동하는 중복된 경우를 방지한다.

 

※ 입력이 주어질 때, N M 순서가 아닌 M N 순서로 주어짐에 유의한다.

 

코드

const sol = (input) => {
  const [M, N] = input[0].split(" ").map(Number); // M,N 순서로 데이터가 주어진다.
  input = input.slice(1);
  const adjM = input.map((row) => row.split("").map(Number));

  function bfs(sx, sy) {
    const deque = [];
    deque.push([sx, sy, 0]);
    const check = Array.from({ length: N }, () => new Array(M).fill(0));
    check[sx][sy] = 1;
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1];
    while (deque.length) {
      const [x, y, cnt] = deque.shift();
      if (x === N - 1 && y === M - 1) return cnt; // (N,M) 위치에 도달하면 종료한다.

      for (let i = 0; i < 4; i++) { // 현재 위치 (x,y)에서 상하좌우 한번씩 이동을 탐색한다.
        const [nx, ny] = [x + dx[i], y + dy[i]];
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (check[nx][ny]) continue;
        check[nx][ny] = 1;
        if (adjM[nx][ny]) {
          adjM[nx][ny] = 0;
          deque.push([nx, ny, cnt + 1]);
        } else {
          deque.unshift([nx, ny, cnt]); // 벽이 없어서 바로 이동하는 경우를 우선적으로 처리하도록 맨 앞에 넣어준다.
        }
      }
    }
  }
  return bfs(0, 0);
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });