[백준/코틀린] 11404번: 플로이드

링크

11404번: 플로이드

풀이

플로이드-워셜(Floyd–Warshall) 알고리즘으로 모든 도시 쌍 간의 최소 비용을 구합니다.

중간 도시 k를 경유하는 경로 graph[i][k] + graph[k][j]가
기존 경로 graph[i][j]보다 짧으면 갱신하는 과정을 모든 k에 대해 반복합니다.

[실전 알고리즘] 0x1C강 - 플로이드 알고리즘

코드

const val MAX = Int.MAX_VALUE / 2
fun main() {
    val n = readln().toInt()
    val m = readln().toInt()
    val graph = List(n) { r -> MutableList(n) { c -> if (r == c) 0 else MAX } }

    repeat(m) {
        val (u, v, w) = readln().split(" ").map { it.toInt() }

        graph[u - 1][v - 1] = minOf(graph[u - 1][v - 1], w)
    }

    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                graph[i][j] = minOf(graph[i][j], graph[i][k] + graph[k][j])
            }
        }
    }

    graph.forEach { row ->
        println(row.map { if (it == MAX) 0 else it }.joinToString(" "))
    }
}

연관 문제

• [백준/코틀린] 11403번: 경로 찾기
• [백준/코틀린] 1389번: 케빈 베이컨의 6단계 법칙