백준[node.js] > 14940번 쉬운 최단거리

문제링크

https://www.acmicpc.net/problem/14940

 

문제풀이

너비우선탐색으로 시작점으로 부터 동서남북으로 탐색하면서 최단거리를 갱신하였다. 

무리없이 풀 수 있었다.

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

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

let s_row = undefined,
    s_column = undefined;

let map = [];
for (let i = 0; i < input.length; ++i) {
    let line = input[i].split(" ").map((n) => Number(n));

    line.forEach((v, column) => {
        if (v === 2) {
            s_row = i;
            s_column = column;
        }
    });
    map.push(line);
}

let answer = Array.from({ length: N }, () => {
    return Array(M).fill(Infinity);
});

answer[s_row][s_column] = 0;

let nextPoint = [[s_row, s_column]];

// 너비우선탐색
while (nextPoint.length) {
    let [now_r, now_c] = nextPoint.shift();
    let now_distance = answer[now_r][now_c];

    // 동서남북
    let dr = [0, 0, 1, -1];
    let dc = [1, -1, 0, 0];

    for (let i = 0; i < 4; ++i) {
        let nextRow = now_r + dr[i];
        let nextColumn = now_c + dc[i];

        if (map[nextRow] && map[nextRow][nextColumn] === 1 && now_distance + 1 < answer[nextRow][nextColumn]) {
            answer[nextRow][nextColumn] = now_distance + 1;
            nextPoint.push([nextRow, nextColumn]);
        }
    }
}

// 최단거리를 갱신하지 못한 곳을 애초에 도달할수 없는 곳(0)과 갈수있는 곳(1)로 구분하여 
// 갈수 있는 곳은 -1 가지 못하는 곳은 0 으로 치환
answer.forEach((line, row) => {
    line.forEach((distance, column) => {
        if (distance === Infinity) {
            if (map[row][column] === 0) {
                answer[row][column] = 0;
            } else if (map[row][column] === 1) {
                answer[row][column] = -1;
            }
        }
    });
});

let str = "";
answer.forEach((row) => {
    str = str + row.join(" ") + "\n";
});

console.log(str.trim());