바이러스(백준)

package com.dofury.kotlin

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Integer.max

class Graph(numVertices: Int){

    var adjLists = Array(numVertices+1) { mutableSetOf<Int>()}

    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 count = br.readLine().toInt()
    val g = Graph(count)
    val connectCount = br.readLine().toInt()

    repeat(connectCount){
        val (src, dest) = br.readLine().split(' ').map { it.toInt() }
        g.addEdge(src,dest)
        g.addEdge(dest,src)
    }
    bw.write("${bfs(g,1)}")


    bw.flush()
    bw.close()
    br.close()

}

fun bfs(graph: Graph, v: Int,): Int{
    val visited = mutableListOf<Int>()

    val queue = ArrayDeque<Int>()
    queue.addLast(v)
    visited.add(v)

    while (!queue.isEmpty()){

        val n = queue.removeFirst()

        for(i in graph.adjLists[n]){
            if(i !in visited){
                queue.addLast(i)
                visited.add(i)
            }
        }
    }
    return if(visited.isEmpty()){0}
    else{ visited.size-1 }
}

케빈 베이컨의 6단계 법칙에 사용했던 그래프 클래스와 BFS 알고리즘을 활용하여 문제를 풀었다.

방문한 노드의 크기만 구하면 되는 쉬운 문제였다. 

중요한건 1에서 부터 시작해서 만나게되는 노드의 수이기 때문에 1 자신을 제외해야한다.