문제

풀이

전형적인 미로 찾기 문제이다. 최단 거리를 구하는 문제이기 때문에 DFS와 BFS로 모두 푸는게 가능하다.
하지만 DFS 같은 경우는 모든 경우의 수를 모두 탐색해서 그 중에 최소값을 찾는 방법이라 시간 복잡도가 BFS에 비해서 오래 걸리기 때문에 최단 거리를 구할 때는 왠만하면 BFS로 푸는게 좋다.

BFS로 풀되 각 그래프 위치별로 check 배열을 만들어 그 전에 위치에 +1을 해줘서 얼마나 갔는지 파악해주는 배열을 따로 만들어줘야한다.

코드

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

const [n, m] = input[0].split(" ").map(Number);

let graph = [];
for (let i = 1; i < n + 1; i++) {
    graph.push([...input[i]]);
}
let ck = Array.from({length: n}, () => new Array(m).fill(0));

let queue = [];
queue.push([0, 0]);
ck[0][0] = 1;

function BFS() {
    let dx = [-1, 0, 1, 0];
    let dy = [0, 1, 0, -1];
    while (queue.length) {
        let [x, y] = queue.shift();
        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 && graph[nx][ny] == 1) {
                ck[nx][ny] = ck[x][y] + 1;
                graph[nx][ny] = 0;
                queue.push([nx, ny]);
            }
        }
    }
}

BFS();
console.log(ck[n-1][m-1]);