[백준/코틀린] 1389번: 케빈 베이컨의 6단계 법칙

링크

1389번: 케빈 베이컨의 6단계 법칙

풀이

플로이드-워셜(Floyd–Warshall) 알고리즘을 사용해 그래프의 모든 노드 쌍에 대한 최단 거리를 구합니다.

임의의 노드 i에서 j로 가는 최단 거리 d[i][j]를 계산하기 위해,
i와 j사이의 중간 노드 k를 경유하는 모든 경로 d[i][k] + d[k][j]를 고려합니다.

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

코드

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    val graph = List(n + 1) { r -> MutableList(n + 1) { c -> if (r == c) 0 else Int.MAX_VALUE / 101 } }

    repeat(m) {
        val (a, b) = readln().split(" ").map { it.toInt() }

        graph[a][b] = 1
        graph[b][a] = 1
    }

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

    println((1..n).minByOrNull { graph[it].sum() })
}