[백준/BOJ] 1719번: 택배

문제

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

1719번: 택배

해설

플로이드 와샬 알고리즘을 응용하여 문제를 해결할 수 있다.

플로이드 와샬을 진행하므로 자기 자신으로 향하는 노드는 0으로, 그 외에는 INF(임의로 지정)으로 초기화해준다.

이후 간선의 정보를 입력받아 어떠한 노드에서 어떠한 노드로 향할 때 얼마의 비용이 드는지를 저장해주고,

a->b와 같이 한 번에 갈 수 있는 노드들은 경로를 저장해 줄 배열 path[a][b] = b와 같이 된다.

이제 플로이드 와샬 알고리즘을 진행하며 더 적은 비용으로 갱신이 가능할 때, 경로 또한 갱신을 해주면 된다.

코드

import kotlin.collections.ArrayList
import kotlin.math.min

data class Route(val node: Int, val cost: Int): Comparable<Route> {
    override fun compareTo(other: Route): Int = cost - other.cost
}

private lateinit var arr: Array<IntArray>
private lateinit var path: Array<IntArray>
private const val INF = 987654321

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }

    arr = Array(n + 1) { IntArray(n + 1) { INF } }
    path = Array(n + 1) { IntArray(n + 1) }

    repeat(n + 1) { i ->
        repeat(n + 1) { j ->
            if(i == j) arr[i][j] = 0
        }
    }

    repeat(m) {
        val (from, to, cost) = readLine().split(" ").map { it.toInt() }
        arr[from][to] = cost
        arr[to][from] = cost
        path[from][to] = to
        path[to][from] = from
    }

    floyd(n)

    for(i in 1 .. n) {
        for(j in 1 .. n) {
            if(path[i][j] != 0) print("${path[i][j]} ")
            else print("- ")
        }
        println()
    }
}

private fun floyd(n: Int) {
    for(k in 1 .. n) {
        for(i in 1 .. n) {
            for(j in 1 .. n) {
                if(arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j]
                    path[i][j] = path[i][k]
                }
            }
        }
    }
}