[백준 2206] 벽 부수고 이동하기 with node.js

📌 문제링크

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

📌 참조

★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★

📌 풀이

• 단순히 좌표만을 큐에 넣어 탐색하는 방식을 넘어, "현재 상태" 자체를 큐에 넣어서 문제를 풀어야 합니다. 즉, 어떤 좌표에 있는가 뿐만 아니라, "여기까지 오면서 벽을 부순 적이 있는가" 여부를 함께 큐에 저장해서 탐색하고, 각각을 별개로 방문체크를 해주어야 한다.
• 참조 보고 힌트를 얻었습니다.

📌 코드

const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString().trim()
    : `6 4
0100
1110
1000
0000
0111
0000`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const resetToShortDistance = (isBrokeWall) => {
  const shortestDistance = Array.from(new Array(N), () => new Array());

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      shortestDistance[i][j] = new Array(2).fill(isBrokeWall);
    }
  }

  return shortestDistance;
};

const getShortestDistance = (startX, startY, isBrokeWall) => {
  const shortestDistance = resetToShortDistance(isBrokeWall);

  const dx = [0, 0, 1, -1];
  const dy = [1, -1, 0, 0];
  const queue = [[startX, startY, isBrokeWall]];
  let queueCursor = 0;

  shortestDistance[startX][startY][isBrokeWall] = 1;

  while (queue.length > queueCursor) {
    const [x, y, isBrokeWall] = queue[queueCursor++];

    if (x === N - 1 && y === M - 1) return shortestDistance[x][y][isBrokeWall];

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

      if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

      let movementWithoutBrokeWall = !map[nx][ny] && !shortestDistance[nx][ny][isBrokeWall];
      if (movementWithoutBrokeWall) {
        queue.push([nx, ny, isBrokeWall]);
        shortestDistance[nx][ny][isBrokeWall] = shortestDistance[x][y][isBrokeWall] + 1;
      }

      let movementBrokeWall = map[nx][ny] && !isBrokeWall;
      if (movementBrokeWall) {
        queue.push([nx, ny, isBrokeWall + 1]);
        shortestDistance[nx][ny][isBrokeWall + 1] = shortestDistance[x][y][isBrokeWall] + 1;
      }
    }
  }

  return -1;
};

const [N, M] = input().split(' ').map(Number);
const map = Array.from(new Array(N), () => input().split('').map(Number));

console.log(getShortestDistance(0, 0, 0));