백준 2178 JS 풀이

구하는 값

(0,0)에서 길따라 (n,m)까지 가는 최단거리

핵심 아이디어

간선 같은 최단거리 ⇒ BFS

graph에 방문하면 0으로 바꿔주면서 방문체크

que에 좌표랑 dep 같이 저장

코드

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

const [n, m] = input[0].split(" ").map(Number);
const graph = [];
for (let i = 1; i <= n; i++) graph.push(input[i].split("").map(Number));

const queue = [];
queue.push([0, 0, 0]);
graph[0][0] = 0;

const dx = [-1, 1, 0, 0],
    dy = [0, 0, -1, 1];

let cnt = 0;
while (queue.length > 0) {
    const [y, x, cur] = queue.shift();

    if (y === n - 1 && x === m - 1) {
        console.log(cur + 1);
        break;
    }
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i],
            ny = y + dy[i];

        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;

        if (graph[ny][nx]) {
            queue.push([ny, nx, cur + 1]);
            graph[ny][nx] = 0;
        }
    }
}