케빈 베이컨의 6단계 법칙

package com.dofury.kotlin

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter



class Graph(numVertices: Int){
    var adjLists: Array<MutableSet<Int>> = Array(numVertices+1) { mutableSetOf() }

    fun addEdge(src: Int, dest:Int) {
        adjLists[src].add(dest)
    }

}

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val results = mutableMapOf<Int, Int>()
    val (userCount, relationCount) = br.readLine().split(' ').map { it.toInt() }

    val g = Graph(userCount)

    repeat(relationCount){
        val (start, dest) = br.readLine().split(' ').map { it.toInt() }
        g.addEdge(start,dest)
        g.addEdge(dest,start)
    }
    repeat(userCount){i ->

        val visited = BooleanArray(userCount+1)

        results[i+1] = bfs(g,i+1,visited)
    }
    val min = results.minOf { it.value }
    val result = results.filter { it.value == min }.minByOrNull { it.key }?.key
    bw.append(String.format("%d",result))
    bw.flush()
    bw.close()
    br.close()

}

private fun bfs(graph: Graph,v: Int,visited: BooleanArray): Int{

    val queue = ArrayDeque<Int>()
    val distance = IntArray(visited.size) {0}
    visited[v] = true
    distance[v] = 0


    queue.addLast(v)

    while (!queue.isEmpty()){
        val n = queue.removeFirst()

        for(i in graph.adjLists[n]){
            if(!visited[i]){
                queue.addLast(i)
                visited[i] = true
                distance[i] = distance[n] +1
            }
        }

    }
    return distance.sum()
}

처음에 문제를 보자마자 그래프를 사용해 풀어야하는 문제인것을 알았으나 구현하는 방법을 몰라서 애를 먹었다.

그래서 그래프 관련 문서를 참고해 구현하였으나, BFS, DFS 중 무엇으로 탐색할지도 생각해야했다.

허나 DFS로는 구현하면 그 값이 최단거리 값을 도출하지못하는 문제가 생겨서 인접한것을

우선으로 탐색하는 BFS를 사용하였다. 

 

그리고 케빈 베이컨수를 구하려고 하였으나 어떻게 구할지 생각하던 찰나 베이컨의 수는 시작 노드에서 다른 노드들의 거리의 합이라는것을 깨달았다.