[백준] 1719_택배 (Javascript)

문제

BOJ1719_택배

풀이

플로이드 워셜 알고리즘을 사용하면 임이의 그래프가 주어졌을 때 모든 노드에서부터 모든 노드까지의 최단 거리를 2차원 배열의 형태로 구할 수 있다.

하지만 이 문제에서 요구하는 것은 최단 거리가 아니라 a에서 b까지 최단 거리로 갈려고 할 때 첫 번째로 방문하는 노드의 번호를 2차원 배열에 저장해야 된다.

그러려면 최단 거리를 담을 2차원 배열과, 정답을 담을 2차원 배열, 총 2개의 2차원 배열이 필요하다.

플로이드 워셜 알고리즘의 점화식은 아래와 같다.

$D_a$$_b$ $=min(D_a$$_b$ , $D_a$$_k$$+D_k$$_b)$

이 말은 a->b로 갈때의 최단거리와 a->k->b 로 갈때 최단거리를 비교하여 더 거리를 $D_a$$_b$ 에 저장해준다는 뜻이다.

정답에서 요구하는데로 응용하면 a->b로 갈때 k를 거쳐 가는 것이 더 빠르다면 a->b로 갈때 첫 번째로 방문하는 노드를 k노드로 설정해주면 되고, 그냥 a->b로 직접 가는 것이 더 빠르다면 첫 번째로 방문하는 노드를 b로 설정해주면 되는 것이다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const path = input.slice(1).map((e) => e.split(' ').map(Number));
const distance = Array.from({ length: n + 1 }, () => Array(n + 1).fill(Infinity));
let arr = Array.from({ length: n + 1 }, () => Array(n + 1));
path.forEach(([s, e, cost]) => {
    distance[s][e] = cost;
    distance[e][s] = cost;
    arr[s][e] = e;
    arr[e][s] = s;
});

// 플로이드 워셜 알고리즘 수행
for (let k = 1; k <= n; k++) {
    for (let a = 1; a <= n; a++) {
        for (let b = 1; b <= n; b++) {
            if (a === b) {
                arr[a][b] = '-';
                continue;
            }
            if (distance[a][b] > distance[a][k] + distance[k][b]) {
                distance[a][b] = distance[a][k] + distance[k][b];
                arr[a][b] = arr[a][k];
            }
        }
    }
}
// 출력 형태로 변환
arr = arr.slice(1).map((e) => e.slice(1));
let answer = '';
arr.forEach((row) => {
    answer += row.join(' ') + '\n';
});
console.log(answer.trimEnd());