[바킹독 강의] 플로이드 와샬

https://blog.encrypted.gg/1035

[실전 알고리즘] 0x1C강 - 플로이드 알고리즘

위 강의자료를 보며 생각해본점들을 기록합니다.

 

 

위 코드를 자바스크립트 코드로 바꾸면 아래와 같다.

const fs = require("fs");

BOJkey = false;

const input = fs
  .readFileSync(BOJkey ? "./ehddud1006/BOJ/11404/input.txt" : "./dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((item) => item.split(" ").map(Number))
  .reverse();

const INF = Number.MAX_SAFE_INTEGER;
const [n] = input.pop();
const [m] = input.pop();

const d = Array.from({ length: 101 }, () => Array(101).fill(INF));

while (input.length > 0) {
  const [a, b, c] = input.pop();
  d[a][b] = Math.min(d[a][b], c);
}

for (let i = 1; i <= n; i++) d[i][i] = 0;
for (let k = 1; k <= n; k++)
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= n; j++)
      if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

let answer = "";
for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
    if (d[i][j] === INF) answer += `0 `;
    else answer += `${d[i][j]} `;
  }
  answer += "\n";
}

console.log(answer);

 

자바스크립트 오버플로우

바킹독님께서는 보통 INF 를 선언할 때 0x7f7f7f7f 를 사용하지시만 이 문제 같은 경우 0x3f3f3f 를 사용하셨다. 그 이유는 C++ 에서 overflow 가 발생하기 때문이다.

나는 보통 INF 을 표현할 때 Number.MAX_SAFE_INTEGER 를 사용하는데, 자바스크립트에서는 이보다 큰 숫자에서 오버플로우가 발생하지만 C++ 처럼 갑자기 작은 수가 튀어나오거나 하지는 않아 그대로 Number.MAX_SAFE_INTEGER 를 사용해도 될 것 같다고 판단했다.

 

아래 예시를 보면 Number.MAX_SAFE_INTEGER 이상의 값이 되면 연산 결과가 예상치 못하는 값이 나오는 것을 알 수 있다.

console.log(Number.MAX_SAFE_INTEGER) // 18014398509481982
console.log(9007199254740992 + 1); // 9007199254740992
console.log(9007199254740992 + 2); // 9007199254740994
console.log(Number.MAX_SAFE_INTEGER + Number.MAX_SAFE_INTEGER) // 18014398509481982
console.log(9007199254740992 + 5); // 9007199254740996

 

 

플로이드의 시간 복잡도

플로이드 알고리즘은 O(n³) 의 시간 복잡도를 가진다. 알고리즘 구현체만 봐도 간단하게 알 수 있었으므로 설명은 생략한다.

O(n³) 의 시간 복잡도를 가지기 때문에 n = 100 까지 넉넉하게 통과할 수 있다.

하지만 플로이드 알고리즘에서는 단순 사칙연산이 주를 이루기 때문에 정점 1000개 정도까지는 플로이드 알고리즘으로 풀어볼만하다고 설명해주셨다.

 

 

대입 과 연산

보통 알고리즘을 푸는 환경에서는 연산보다 대입이 느리다고 한다.

그 이유는 대입 연산자를 사용할 경우에는 메모리에 접근해야한다. 반면 사칙연산 같은 경우 캐시 메모리에 있는 값으로 대부분 연산이 이루어지기 때문에 더 속도가 빠르다.

 

따라서 플로이드 알고리즘 처럼 시간복잡도가 크게 나오는 로직을 푸는 경우에 무조건 대입이 사용되는 1번 로직보다는 2번 로직이 조금이나마 속도를 개선할 수 있다는 팁을 주셨다.

// 1
for (let k = 1; k <= n; k++)
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= n; j++)
      d[i][j] = min(d[i][k] + d[k][j], d[i][j];
      
      
// 2
for (let k = 1; k <= n; k++)
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= n; j++)
      if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

 

플로이드 와샬 경로 복원

 

자바스크립트로 변환한

const fs = require("fs");

BOJkey = false;

const input = fs
  .readFileSync(BOJkey ? "./ehddud1006/BOJ/11780/input.txt" : "./dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((item) => item.split(" ").map(Number))
  .reverse();

const INF = Number.MAX_SAFE_INTEGER;
const [n] = input.pop();
const [m] = input.pop();

const d = Array.from({ length: 101 }, () => Array(101).fill(INF));
const nxt = Array.from({ length: 101 }, () => Array(101).fill(INF));

while (input.length > 0) {
  const [a, b, c] = input.pop();
  d[a][b] = Math.min(d[a][b], c);
  nxt[a][b] = b;
}

for (let i = 1; i <= n; i++) d[i][i] = 0;
for (let k = 1; k <= n; k++)
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= n; j++)
      if (d[i][k] + d[k][j] < d[i][j]) {
        d[i][j] = d[i][k] + d[k][j];
        nxt[i][j] = nxt[i][k];
      }

let answer = "";
for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
    if (d[i][j] === INF) answer += `0 `;
    else answer += `${d[i][j]} `;
  }
  answer += "\n";
}

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
    let target = nxt[i][j];
    if (target === INF) answer += "0\n";
    else {
      let count = 2;
      let tempString = "";
      tempString += `${target} `;
      while (target !== j) {
        target = nxt[target][j];
        tempString += `${target} `;
        count++;
      }
      tempString = `${count} ${i} ${tempString}\n`;
      answer += tempString;
    }
  }
}

console.log(answer);