[백준] 11403 경로찾기 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

let N = +input.shift();
let arr = [];

for (const row of input) {
  arr.push(row.split(" ").map(Number));
}

for (let k = 0; k < N; k++) {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (arr[i][k] && arr[k][j]) {
        arr[i][j] = 1;
      }
    }
  }
}

for (let i = 0; i < N; i++) {
  console.log(arr[i].join(" "));
}

✔ 알고리즘 : 플로이드-와샬

✔ 경로가 존재하는지 확인하는 플로이드 와샬 문제이므로 3중 for문을 통해 i로부터 j까지의 경로가 존재하는지 확인

✔ 난이도 : 백준 기준 실버 1