🎲 백준 11780번 플로이드 2

백준 11780번

🧸 플로이드 와샬 알고리즘에 익숙해질 수 있는 문제라고 생각이 든다.
💊 Infinity를 0으로 처리해주야한다!!

코드

const fs = require('fs'); 
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const M = +input.shift();
input = input.map((el) => el.split(" ").map(Number));
const arr = Array.from(new Array(N + 1), () => new Array(N + 1).fill(Infinity));
const way = Array.from(new Array(N + 1), () => new Array(N + 1).fill([]));

for (let n = 1; n < N + 1; n++) {
  arr[n][n] = 0;
}
for (let m = 0; m < M; m++) {
  arr[input[m][0]][input[m][1]] = Math.min(
    arr[input[m][0]][input[m][1]],
    input[m][2]
  );
}

const floydWarshall = () => {
  for (let k = 1; k < N + 1; k++) {
    for (let i = 1; i < N + 1; i++) {
      for (let j = 1; j < N + 1; j++) {
        if (arr[i][k] + arr[k][j] < arr[i][j]) {
          arr[i][j] = arr[i][k] + arr[k][j];
          //경로 저장
          way[i][j] = [...way[i][k], k, ...way[k][j]];
        }
      }
    }
  }
};

floydWarshall();

//최소 비용 출력
for (let i = 1; i < N + 1; i++) {
  let string = "";
  for (let j = 1; j < N + 1; j++) {
    if (arr[i][j] === Infinity) {
      string += 0 + " ";
      continue;
    }
    string += arr[i][j] + " ";
  }
  console.log(string);
}

//경로 출력
for (let i = 1; i < N + 1; i++) {
  for (let j = 1; j < N + 1; j++) {
      if (i === j || arr[i][j]===Infinity) {
      console.log(0);
      continue;
    }
    let string = way[i][j].length + 2 + " " + i + " ";
    if (way[i][j].length) string += way[i][j].join(" ") + " ";
    string += j;
    console.log(string);
  }
}