[javascript] 백준 2206번 벽 부수고 이동하기

문제보기

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

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

const map = input.map((item) => item.split("").map((value) => +value));

// 방문체크 배열 3차원 배열로 (벽을 부수지 않은 경우, 벽을 부순 경우) 2개로 나눈다.
const visited = Array.from({ length: 2 }, () =>
    Array.from({ length: N }, () => Array.from({ length: M }).fill(false))
);

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

if (N === 1 && M === 1) return console.log(1);

const BFS = (start) => {
    let queue = [[...start, false, 1, 0]]; // 순서대로(시작지점, 벽을 부쉈는지 여부, 이동횟수, 방문체크 배열 z축 위치)
    let i = 0;
    while (queue.length > i) {
        let [y, x, destroy, count, z] = queue[i];
        i++;
        visited[z][y][x] = true;
        if (y === N - 1 && x === M - 1) return count;
        for (let i = 0; i < direction.length; i++) {
            const [dy, dx] = [y + direction[i][0], x + direction[i][1]];
            if (dy < 0 || dx < 0 || dy >= N || dx >= M || visited[z][dy][dx])
                continue;
            if (dy === N - 1 && dx === M - 1) return count + 1;
            if (destroy) { // 벽을 부순 경우에는
                if (map[dy][dx] === 1) continue;
              // 방문체크 z축을 이동하여 탐색한다
                queue.push([dy, dx, true, count + 1, 1]);
            } else {
                if (map[dy][dx] === 0)
                    queue.push([dy, dx, false, count + 1, 0]);
              // 다음에 벽을 부수게 된다면
                if (map[dy][dx] === 1) queue.push([dy, dx, true, count + 1, 1]);  // 방문체크 z축을 이동하여 탐색한다
            }
            visited[z][dy][dx] = true;
        }
    }
  // queue를 다 탐색했는데 목적지에 도달하지 못한다면 -1 출력
    return -1;
};

console.log(BFS([0, 0]));

풀이
이미 벽을 부순적이 있는 경우가 방문처리를 해버리는 바람에 부순적이 없는 경우가 접근해야 하는곳도 방문처리가 되어 결과를 제대로 도출할수가 없었다.
해결방법은 벽을 부순적이 있는지, 없는지에대해 방문여부를 3차원 배열로 만들어서
벽을 부수게 된다면 이후에는 z축으로 이동해서 진행하고 벽은 부순적이 없다면 계속 진행하면된다

queue 자료구조에 shift()를 사용하면 최대 100만개 크기인 이번 문제에서는 시간초과가 발생하기 떄문에 i라는 인덱스를 부여해서 while문이 1회 반복될때마다 i에 1을 더해주는 방식으로 queue를 순서대로 탐색하였다.