백준[JS] > 11403번 경로 찾기

문제링크

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

풀이

문제를 풀긴 풀었는데 플로이드 와샬의 점화식을 이용하진 않았다. 해당 점화식을 이용해서 풀면 더 짧은 코드로 작성이 가능하다. 나는 하나의 점을 방문하면서 기존 graph를 갱신하는 방향으로 문제를 풀고 이미 방문한 점은 다시 방문하지 않는 방식으로 계산을 최적화 하였다.

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let [pointsCnt, ...arr] = input;

let graph = arr.map((str) => {
    return str.split(" ").map((n) => Number(n));
});

// 방향성이 존재하는 간선
for (let r = 0; r < graph.length; ++r) {
    visited = [];
    toVisit = [];
    for (let c = 0; c < graph[0].length; ++c) {
        if (graph[r][c] === 1) {
            toVisit.push(c);
            visited.push(c);
        }

        while (toVisit.length) {
            let point = toVisit.shift();
            for (let z = 0; z < graph[0].length; ++z) {
                if (graph[point][z] === 1 && !visited.includes(z)) {
                    graph[r][z] = 1;
                    toVisit.push(z);
                    visited.push(z);
                }
            }
        }
    }
}

let answer = "";
graph.forEach((line) => {
    let str = line.join(" ");
    answer += str + "\n";
});
console.log(answer);

하단은 플로이드 와샬 점화식으로 문제를 풀었을 경우이다.

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let [pointsCnt, ...arr] = input;

let graph = arr.map((str) => {
    return str.split(" ").map((n) => Number(n));
});

// 방향성이 존재하는 간선이네

for(let k=0; k<graph.length; ++k){
    for(let r=0; r<graph.length; ++r){
        for(let c=0; c<graph[0].length; ++c){        
            if(graph[r][k]&&graph[k][c]){
                 graph[r][c]=1   
            }
        }
    }
}
let answer = "";
graph.forEach((line) => {
    let str = line.join(" ");
    answer += str + "\n";
});
console.log(answer);