[백준-Gold4] 11404 플로이드 - javascript

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

11404번: 플로이드

 

 

 

[풀이]

 

 

 노드 --------간선-------> 노드

(도시)             버스              (도시)

 

예제) 

도시 5개

버스 14개

 

시작점 끝점 비용 

1        2        2

...

 

 

 

 

* 플로이드 알고리즘 설명 참고 : https://eonhwa-theme.tistory.com/178

[코딩테스트 알고리즘] 플로이드-워셜 - javascript

 

 

🧊 한 점 에서 모든점 : 다익스트라 사용

🧊 모든점 에서 모든점 : 플로이드 사용 

    🧊 거리 초기값 무한대로 설정, 자기 자신으로 가는 값 0으로 설정

    🧊 노드 거쳐서 가서 비용 작아질 경우 값 갱신

    🧊 시간복잡도 : V^3

 

 

해당 문제는 십만

플로이드 사용할 경우(n=100), 100^3 하면 === 10^6     (>10^5) 가능

 

거리 배열 : int[][]
- 비용 최대 : 1e5 * 1e2 === 1e7 > INT 가능

 

 

 

1️⃣ 비용 배열 INF 로 초기화 : rs

const INF = Number.MAX_SAFE_INTEGER;

const rs = Array.from(Array(parseInt(n) + 1), () => Array(parseInt(n) + 1).fill(INF));

 

 

2️⃣ 시작점 === 끝점 0으로 초기화

for (let i = 1; i <= parseInt(n); i++) {
  rs[i][i] = 0;
}

 

 

3️⃣ rs [시작점] [끝점] = 최소값 비교해서 최소 대입

for (let i = 0; i < parseInt(m); i++) {
  const [a, b, c] = arr[i].split(' ').map(Number);
  rs[a][b] = Math.min(rs[a][b], c);
}

 

 

4️⃣ 플로이드 이용 (3중 for문 )

for (k){ // 거치는 값
	for (j) { // 시작
    		for (i) { //도착
        
    }
}

 

j --------> k --------> i

 

만약 ( j-> i ) 가 ( j->k ) + ( k -> i) 보다 크다면

 ( j->k ) + ( k -> i)  값을  ( j-> i )  으로 갱신해줘라

if (rs[j][i] > rs[j][k] + rs[k][i]) {
	rs[j][i] = rs[j][k] + rs[k][i];
}

 

 

 

 

5️⃣ 마지막 리턴

 

 

 

 

 

 

 

 

[최종 코드]

 

/**
 * 아이디어
 * - 모든점 -> 모든점 :  플로이드 와샬
 * - 비용배열 INF로 초기화
 * - 간선의 비용 대입
 * - 거쳐서 비용 줄어들 경우, 갱신(for문 3중첩)
 * 
 * 변수 
 * - 비용 배열 : int[][] 
 */


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 INF = Number.MAX_SAFE_INTEGER;

const rs = Array.from(Array(parseInt(n) + 1), () => Array(parseInt(n) + 1).fill(INF));

for (let i = 1; i <= parseInt(n); i++) {
  rs[i][i] = 0;
}

for (let i = 0; i < parseInt(m); i++) {
  const [a, b, c] = arr[i].split(' ').map(Number);
  rs[a][b] = Math.min(rs[a][b], c);
}

for (let k = 1; k <= parseInt(n); k++) {
  for (let j = 1; j <= parseInt(n); j++) {
    for (let i = 1; i <= parseInt(n); i++) {
      if (rs[j][i] > rs[j][k] + rs[k][i]) {
        rs[j][i] = rs[j][k] + rs[k][i];
      }
    }
  }
}

for (let j = 1; j <= parseInt(n); j++) {
    let result = '';
    for (let i = 1; i <= parseInt(n); i++) {
        if (rs[j][i] === INF) result += '0 ';
        else result += rs[j][i] + ' ';
    }
    console.log(result.trim());
}