[node.js] 미로 탐색 ( 백준 2178번 )

// 백준 2178번 미로 탐색을 풀었습니다.
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let input = [];
let N = 0;
let M = 0;
rl.on("line", (line) => {
    if (!N) {
        [N, M] = line.split(" ").map(Number);
    } else {
        input.push(line);
        if (input.length === N) {
            main();
            process.exit();
        }
    }
});

const main = () => {
    const graph = [];
    const visited = [];

    for (let i = 0; i < N; i++) {
        graph[i] = input[i].split("").map(Number);
        visited[i] = new Array(M).fill(0);
    }

    const bfs = (yPos, xPos) => {
        const xMove = [0, 0, -1, 1];
        const yMove = [1, -1, 0, 0];
        const queue = [];
        queue.push({ yPos: yPos, xPos: xPos });
        visited[yPos][xPos] = 1;

        while (queue.length) {
            const { yPos, xPos } = queue.shift();
            for (let i = 0; i < 4; i++) {
                const nextY = yPos + yMove[i];
                const nextX = xPos + xMove[i];
                if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
                    if (!visited[nextY][nextX] && graph[nextY][nextX]) {
                        visited[nextY][nextX] = visited[yPos][xPos] + 1;
                        queue.push({ yPos: nextY, xPos: nextX });
                    }
                }
            }
        }
    };

    bfs(0, 0);
    console.log(visited[N - 1][M - 1]);
};

미로 탐색 문제처럼 테스트 케이스가 1개씩만 주어지면 좋겠다.
N개의 입력을 받을 수 있단 문제는 자바스크립트 유저에게는 지옥이다.

문제마다 체크해야 할 요소가 있는데, 일단 N과 M의 순서가 어떻게 나오는가.
이전 문제는 M,N의 순서로 나왔다.
다음은 입력이 어떻게 나오는가, 배열의 모습이다.
아까 문제는 "0 0 0 0 0"... 과 같이, 공백 문자들을 두고 나왔는데, 이번에는 "00000"처럼 붙은 상태로 나왔다.
split을 어떻게 하는지가 달라진다.

그 후에는 간단하다.

이 문제는 일단 dfs로는 풀 수 없는 유형이다.
dfs는 도착하는 건 구할 수 있어도 최단 거리를 알 방법이 없다. 백 트래킹?
아니면 visited에 저장한 값이 현재 것보다 큰 경우에는 갈 수 있다고 조건을 건다?
어떻게 하느냐에 따라 어쩌면 풀 수 있을지도 모르겠지만 그건 이미 dfs라는 알고리즘 범위를 넘어선 것이 된다.

차라리 bfs가 낫다.