[백준] 11404 플로이드 - javascript

📌 문제

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

📌 풀이

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

const [n, m, ...arr] = input;
const busInfo = arr.map(a => a.split(" ").map(Number));
const dist = Array.from({ length: +n + 1 }, () =>
  Array.from({ length: +n + 1 }, () => Infinity)
);

busInfo.forEach(
  bus => (dist[bus[0]][bus[1]] = Math.min(bus[2], dist[bus[0]][bus[1]]))
);

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 (dist[i][k] + dist[k][j] < dist[i][j] && i !== j) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

for (let i = 1; i < +n + 1; i++) {
  for (let j = 1; j < +n + 1; j++) {
    if (dist[i][j] === Infinity) dist[i][j] = 0;
  }
}

dist.slice(1).map(t => {
  console.log(t.slice(1).join(" "));
});

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

✔ 다익스트라와 같은 최단경로 그래프 알고리즘인 플로이드-와샬 문제이다. 모든 정점에서의 정점까지의 최단거리를 구할 때 사용되는 알고리즘 이다.

✔ 3중 for문을 사용하여 최단 거리를 갱신해 나간다.

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 (dist[i][k] + dist[k][j] < dist[i][j] && i !== j) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

k는 거쳐가는 경유지 i는 시작점 j는 도착점이다. dist[i][k] + dist[k][j] 즉 k를 거쳐서 i에서 j까지 가는 경로의 비용값이 dist[i][j]보다 작을 경우에 갱신해준다.

✔ Infinity인 경우는 갈 수 없는 경우이므로 문제에서 0으로 처리하라 했으므로 3중 for문이 끝난 후 값을 변경시킨다.

for (let i = 1; i < +n + 1; i++) {
  for (let j = 1; j < +n + 1; j++) {
    if (dist[i][j] === Infinity) dist[i][j] = 0;
  }
}

❗ 3중 for문 안에서 시작점과 도착점이 같은 경우만 0으로 갱신해주면 98%에서 틀렸습니다를 받는다

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 (tmp[i][k] + tmp[k][j] < tmp[i][j] && i !== j) {
        tmp[i][j] = tmp[i][k] + tmp[k][j];
      }
      if (i === j) tmp[i][j] = 0;
    }
  }
}

시작점과 도착점이 같지 않더라도 Infinity, 즉 갈 수 없는 경우를 고려해야 한다.

✔ 난이도 : 백준 기준 골드 4