백준 11404 - 플로이드 (Kotlin)

11404번: 플로이드

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을 출력한다.

 

---

알고리즘 분류

• 그래프 이론
• 최단 경로
• 플로이드-워셜

---

해설

이번 문제는 플로이드-워셜 알고리즘을 사용하여 해결해야 한다.

 

플로이드-워셜 알고리즘을 알고 있다면 매우 쉽게 해결할 수 있는 문제이다.

플로이드-워셜 알고리즘에 대하여 간단하게 설명하자면 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용되는 알고리즘이다.

 

예를 들자면, A노드에서 C노드까지의 거리가 20이라고 가정하자.

이 때, A노드에서 B노드까지 거리가 10, B노드에서 C노드까지 거리가 5라고 하면 cost[A][C] 의 값은 20 → 15로 변하는 것이다.

 

즉, 10개의 노드가 있다고 가정하면 어떤 노드에서 다른 노드까지 갈 때, 모든 노드를 거쳐가는 경우의 수 중 가장 짧은 거리로 갱신하는 알고리즘이다.

 

시작점을 i, 도착점을 j , 경유지점을 k 라고 한다면

bus[i][j] = minOf(bus[i][j], bus[i][k] + bus[k][j] 가 되는 것이다.

 

여기서 중요한 점이 있다.

INF 값을 Int.MAX_VALUE 로 지정하게 되면 더하는 연산에서 음수가 되어버려 정확한 답을 출력하지 못한다.

고로 적당한 큰 수인 1000000000 을 지정하여 연산을 수행해야 정답처리가 된다.

(그렇지 않다면 97% ~ 98%에서 틀렸다고 나온다)

 

---

전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader

private const val MAX = 1000000000
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val size = br.readLine().toInt()
    val cnt = br.readLine().toInt()
    val bus = Array(size) { Array(size) { MAX } }

    repeat(size){
        bus[it][it] = 0
    }

    repeat(cnt) {
        val (s, d, c) = br.readLine().split(" ").map { it.toInt() }
        if(bus[s - 1][d - 1] > c){
            bus[s - 1][d - 1] = c
        }
    }

    for (k in 0 until size) {
        for (i in 0 until size) {
            for (j in 0 until size) {
                if (bus[i][j] > bus[i][k] + bus[k][j]) {
                    bus[i][j] = bus[i][k] + bus[k][j];
                }
            }
        }
    }

    for(i in 0 until size){
        for(j in 0 until size){
            val cost = if(bus[i][j] >= MAX) 0 else bus[i][j]

            print("$cost ")
        }
        println()
    }
}

 

---

정답

 

 

최단 경로를 구하는 문제가 주어졌을 때, 플로이드-워셜 알고리즘을 써야하는지, 다익스트라 알고리즘을 사용해야하는지에 대한 구분이 어렵다.

또한 둘을 비교했을 때 무엇을 사용하는 것이 더 나은 방식인지에 대한 고민이 필요할 것 같다.