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

문제

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

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

해설

bfs로도 풀 수 있겠지만, 나는 이런 문제를 플로이드 와샬 알고리즘을 사용하여 모두 구해놓은 후 그 값들을 통해 해결하는 편을 좋아한다.

배열에서 자기 자신으로 가는 경우의 수는 0으로 초기화해주고, 나머지는 INF(987654321)의 값으로 초기화해주었다.

후에 입력받은 관계 (a, b라 하자)를 1로 저장한다. 즉, arr[a][b] = 1, arr[b][a] = 1인 것이다.

이 문제에선 친구 관계는 양방향이기 때문이다.

이제 플로이드 와샬 알고리즘을 수행시켜 모든 관계에 대한 경우의 수를 구한다.

그렇다면 1번 사람에게서 2~5번 친구와의 관계를 구할 수 있을 것이다.

이 모든 관계값을 더한 것이 케빈 베이컨 수가 되고 이가 가장 작은 사람이 답이 된다.

코드

import kotlin.math.min

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

fun main() = with(System.`in`.bufferedReader()) {
    val (userCnt, relationCnt) = readLine().split(" ").map { it.toInt() }
    arr = Array(userCnt + 1) { IntArray(userCnt + 1) { INF } }

    for(i in 1 .. userCnt) {
        for(j in 1 .. userCnt) {
            if(i == j) arr[i][j] = 0
        }
    }

    repeat(relationCnt) {
        val (a, b) = readLine().split(" ").map { it.toInt() }
        arr[a][b] = 1
        arr[b][a] = 1
    }

    floyd(userCnt)

    var min = Integer.MAX_VALUE
    var user = 0
    for(i in 1 .. userCnt) {
        var sum = 0
        for(j in 1 .. userCnt) {
            sum += arr[i][j]
        }

        if(min > sum) {
            min = sum
            user = i
        }
    }

    println(user)
}

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