[JS] 백준 11404번 : 플로이드 - 그래프이론, 플로이드-와샬

https://www.acmicpc.net/status?user_id=oridori2705&problem_id=11404&from_mine=1 

채점 현황

전형적인 플로이드 와샬 알고리즘문제이다.

 

플로이드 와샬 알고리즘이란?

기존에 다익스트라 알고리즘은 [하나의 정점에서 출발 했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘]입니다.

만약 [모든 정점에서 모든 정점으로의 최단 경로]를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야합니다.

https://ydoag2003.tistory.com/42

플로이드 와샬(Floyd warshall)알고리즘

-여기에 설명이 있으니 참고하자.

 

 

 

풀이방법

1. n x n의 크기의 2차원 배열인 floyd에서 모든 값을 Infinity 값으로 초기화한다.

2. 주어진 a에서 b로 가는 비용인 c를 floyd배열에 floyd[a][b]=c 로 값을 넣는다.

 -즉 a열에서 b행은 a도시에서 b도시로가는 비용 c이다.

 

3. 이때 a->a로 가는 버스는 없다는 조건을 보자

 -1. 이 조건을통해서 a->a 즉, 0열->0열의 값은 0으로 넣어줘야한다.

 -2. 아니면 나중에 최소비용을 구할때 i열과 j행의 값이 같을 때는 검사를 하지않고 넘어간 다음 나중에 INF값을 0으로 바꿔주면 된다.

4. 이때 a->b로 가는 버스가 다수인 조건을 보자

 - 3 - > 5로 가는 버스가 두 개가 주어진다.

 - 그러면 이 버스 중 c가 최소 비용 값으로 해줘야한다.

5. 3중 for문으로 진행하고 k를 기준으로 i열과 j행을 순회한다.

 -k는 k를 거쳐갈 때의 값을 뜻한다.

  ->즉, i열,j행의 값에서 만약 i열,k행 + k열,j행 값과 비교했을 때 k를 거쳐갔을 때의 값이 작다면 그 값이 최소비용이 되므로 바꿔줘야한다.

6.위와 같이 K를 기준으로 모두 갱신하면 모든 값이 최소비용으로 된 배열 나오게 된다.

 

 

🤟내 제출

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

let [n, m, ...bus] = input;
n = Number(n);
m = Number(m);
const arr = bus.map((a) => a.split(" ").map(Number));

let floyd = Array.from({ length: n }, () => Array(n).fill(Infinity));

arr.forEach((tt) => {
  let [a, b, c] = tt;
  floyd[a - 1][a - 1] = 0;
  floyd[b - 1][b - 1] = 0;
  floyd[a - 1][b - 1] = Math.min(floyd[a - 1][b - 1], c);
});

for (let k = 0; k < n; k++) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (floyd[i][k] + floyd[k][j] < floyd[i][j]) {
        floyd[i][j] = floyd[i][k] + floyd[k][j];
      }
    }
  }
}
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (floyd[i][j] === Infinity) floyd[i][j] = 0;
  }
}
console.log(floyd.map((v) => v.join(" ")).join("\n"));

 

 

어려웠던 점

1. 플로이드 와샬 알고리즘이라는 것을 빨리 파악하지 못했다.

-처음에 다익스트라인줄 알았지만 모든 정점에서 모든 정점은 플로이드 와샬이다.

2.시간초과

- JS로 풀게되면 주어진 입력값을 가져올 때 주의해야한다.

-나는 보통 아래와 같이 shift()를 이용해서 가져왔는데 이게 시간초과의 원인이였다.

- 이 shift로도 시간초과가 날 수 있으니 조심하자

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

let n = Number(input.shift());
let m = Number(input.shift());
let arr = [];
for (let i = 0; i < m; i++) {
  arr.push(input.shift().split(" ").map(Number));
}


...

3. 플로이드 와샬에서의 조건 쓰는 방법 두 가지

 -플로이드 와샬을 진행할 때 1->1은 0이어야한다.

 -나는 아래와 같이 미리 0값을 넣어주는 방법을 택했다.

...


arr.forEach((tt) => {
  let [a, b, c] = tt;
  floyd[a - 1][a - 1] = 0;
  floyd[b - 1][b - 1] = 0;
  floyd[a - 1][b - 1] = Math.min(floyd[a - 1][b - 1], c);
});

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

...

 

-하지만 아래와 같이 i행과 i열이 같을 때는 넘어가주는 방법도 가능하다.

...

arr.forEach((tt) => {
  let [a, b, c] = tt;
  floyd[a - 1][b - 1] = Math.min(floyd[a - 1][b - 1], c);
});
for (let k = 0; k < n; k++) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (floyd[i][k] + floyd[k][j] < floyd[i][j] && i !== j) {
        floyd[i][j] = floyd[i][k] + floyd[k][j];
      }
    }
  }
}

...

-이 때 중요한 점은 모든 검사가 끝나고 아래와 같이 Infinity 값을 0으로 바꿔줘야한다.

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