🎲 백준 2206번 벽 부수고 이동하기

백준 2206번

💡 이동 가능 구역에 왔을 때, 벽을 뚫고 왔는지 벽을 안 뚫고 왔는데 두 가지 경우가 있을 수 있어 checked배열을 3차원으로 만들어주었다.
💊 N,M이 1일 때 경우도 처리해주어야한다.
💊 shift()를 해주면 시간초과가 발생하여 index를 증가시키는 방법을 사용했다.
🎨 반례모음

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M] = input.shift().split(" ").map(Number);
const map = input.map((el) => el.split("").map(Number));

const dir = [
  [0, 1],
  [1, 0],
  [0, -1],
  [-1, 0],
];

let answer = -1;
const checked = Array.from(new Array(N), () =>
  Array.from(new Array(M), () => new Array(2).fill(false))
);
const bfs = () => {
  const queue = [[0, 0, false, 1]];
  checked[0][0][0] = true;
  checked[0][0][1] = true;
  let index = 0;
     if (N === 1 && M === 1) {
    answer = 1;
    return;
  }
  while (queue.length > index) {
    const [locY, locX, crush, distance] = queue[index];
    for (let d = 0; d < 4; d++) {
      const nextY = locY + dir[d][0];
      const nextX = locX + dir[d][1];

      if (
        nextX < 0 ||
        nextY < 0 ||
        nextX >= M ||
        nextY >= N ||
        map[nextY][nextX] === -1
      )
        continue;

      if (nextY === N - 1 && nextX === M - 1) {
        answer = distance + 1;
        return;
      }

      if (map[nextY][nextX] === 0) {
        //이동 가능 구역
        //벽 뚫고 옴
        if (crush && !checked[nextY][nextX][0]) {
          queue.push([nextY, nextX, crush, distance + 1]);
          checked[nextY][nextX][0] = true;
        }
        //벽 안 뚫고 옴
        if (!crush && !checked[nextY][nextX][1]) {
          queue.push([nextY, nextX, crush, distance + 1]);
          checked[nextY][nextX][1] = true;
        }
      } else {
        //벽
        //벽 뚫은 적 없다면
        if (!crush) {
          queue.push([nextY, nextX, true, distance + 1]);
          map[nextY][nextX] = -1;
        }
      }
    }
    index++;
  }
};

bfs();

console.log(answer);