[백준] 케빈 베이컨 (1389)(Kotlin)

원본 문제 : https://www.acmicpc.net/problem/1389

문제 참고(Floyd Warshall) : https://hyeooona825.tistory.com/61

 

<첫번째 - 플로이드와샬> 실패

 

import java.io.*
import java.util.*

var map: Array<IntArray> = arrayOf()
var persons: Int = 0

val INF: Int = 10000000


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    var str = readLine().split(" ")

    persons = str[0].toInt()
    var net: Int = str[1].toInt()
    map = Array( persons ) { IntArray( persons ) }

    for ( i in 0 until persons ) {
        for ( j in 0 until persons ) {
            if ( i == j ) map[i][j] = 0
            else map[i][j] = INF
        }
    }

    for ( i in 0 until persons ) {
        str = readLine().split(" ")

        val x: Int = str[0].toInt() - 1
        val y: Int = str[1].toInt() - 1

        map[x][y] = 1
        map[y][x] = 1
    }

    floyd()

    var list: MutableMap<Int, Int> = mutableMapOf()

    for ( i in 0 until persons ) {
        list.put(i, 0)
        for ( j in 0 until persons ) {
            list[i] = list.getValue(i) + map[i][j]
        }
    }

    print(list.toList().sortedBy { (_, value) -> value }.get(0).first + 1)

}


fun floyd() {
    for ( k in 0 until persons ) {
        for ( i in 0 until persons ) {
            for ( j in 0 until persons ) {
                map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j])
            }
        }

    }
}