백준(11403)_플로이드와샬.md

백준(11403)_플로이드와샬

---

const fs = require('fs');
const stdin = (process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `3
0 1 0
0 0 1
1 0 0`
).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();


const N = parseInt(input())

let graph = Array(N).fill(Array(N).fill(0))

//input
for (let i = 0; i < N; i++) {
    graph[i] = input().split(' ').map((A) => parseInt(A))

}

//floyd-warshall
for (let via = 0; via < N; via++) {
    for (let from = 0; from < N; from++) {
        for (let to = 0; to < N; to++) {
            if (graph[from][via] == 1 && graph[via][to] == 1)
                graph[from][to] = 1;
        }
    }
}

//print
for (let i = 0; i < N; i++) {
    console.log(graph[i].join(' '))
}

---

플로이드-와샬 알고리즘! 연결된 모든 곳을 알아내야할 때 사용하면 쉽게 답을 얻어낼 수 있다.

//floyd-warshall
for (let via = 0; via < N; via++) {
    for (let from = 0; from < N; from++) {
        for (let to = 0; to < N; to++) {
            if (graph[from][via] == 1 && graph[via][to] == 1)
                graph[from][to] = 1;
        }
    }
}
//from에서 to로 가는데 via에 거쳐서 갈 수 있다면 1로 바꾼다.