[백준] 11404번: 플로이드

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

예제 입출력

풀이

플로이드 와샬 알고리즘을 사용하여 문제를 풀었다.
출발지와 도착지가 같은 버스 노선이 있어서 그중에 최소값만 map 배열에 넣었다.
출발지에서 도착지까지 가는 시간과 중간 지점을 거쳐서 도착지까지 가는 시간을
비교하여 작은 값을 넣어 map을 재할당한다.
만약 출발지와 도착지와 같다면 continue() 한다.
출력할 때 무한대 값을 0으로 바꾼뒤 join()을 이용하여 문자열로 출력한다.

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(str => str.split(' ').map(Number));
const [country, bus] = [input[0][0], input[1][0]]
const input_map = input.slice(2);
let map = Array.from(Array(country), () => new Array(country).fill(Infinity));
input_map.forEach((value) => {
    let [x, y, dis] = value;
    if (map[x - 1][y - 1] > dis) map[x - 1][y - 1] = dis;
})
for (let mid = 0; mid < country; mid++) { // 중간
    for (let start = 0; start < country; start++) { // 출발
        for (let end = 0; end < country; end++) { // 도착
            if (start === end) continue;
            if (map[start][end] > map[start][mid] + map[mid][end])
                map[start][end] = map[start][mid] + map[mid][end]
        }
    }
}
for (let i = 0; i < country; i++) {
    for (let k = 0; k < country; k++) {
        if (map[i][k] === Infinity) map[i][k] = 0;
    }
    console.log(map[i].slice(0, country).join(" "));
}

회고

플로이드 와샬은 출발지에서 모든 경로까지의 최소 비용을 출력해주고
다익스트라는 출발지에서 특정 경로까지의 최소 비용을 구해준다.
처음에 DFS로 풀었는데 시간 초과가 발생했다.

백준에서 입력값을 변수에 할당하는 과정이 까다로웠다.
vscode 상에서는 제대로 출력이 되는데 백준에서는 런타임 에러(rangeError)가
발생했다. 이유는 아직 찾지 못했다.

최초 코드

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\r\n")
const [country, bus] = [Number(input[0]), Number(input[1])]
const input_map = input.slice(2);
let map = Array.from(Array(country), () => new Array(country).fill(Infinity));
input_map.forEach((value) => {
    let [x, y, dis] = value.split(" ").map(Number);
    if (map[x - 1][y - 1] > dis) map[x - 1][y - 1] = dis;
})