[백준] 2606 - 바이러스

무방향 비연결 그래프를 BFS 나 DFS 를 활용하여 첫방문하는 곳마다 Count 를 증가시킨 뒤, 이를 출력하는 문제이다.

이전까지의 문제들을 풀어왔다면 그리 어렵지 않게 풀 수 있다.

풀이

/*
* 무방향 비연결 그래프
*
* 첫째 줄 - 컴퓨터 수
* 컴퓨터의 수는 1 ~ 100.
* 각 컴퓨터에는 1번부터 차례대로 번호가 매겨짐.
*
* 둘째 줄 - 컴퓨터 쌍의 수
* 쌍의 수만큼의 줄에서 번호쌍 주어짐
*
* 1번 컴퓨터가 걸리면 걸리게 되는것. 즉, visited 인 것들만 찾으면 된다.
*
* bfs, dfs 아무렇게나 풀어도 상관 없을듯
* */
fun `2606-바이러스`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val computerCount = br.readLine().toInt()
    val pairCount = br.readLine().toInt()
    val visitedArr = BooleanArray(computerCount + 1)
    val adjacencyList = Array(computerCount + 1){ mutableListOf<Int>() }
    val queue = ArrayDeque<Int>()
    var count = 0

    repeat(pairCount){
        val token = java.util.StringTokenizer(br.readLine())
        val from = token.nextToken().toInt()
        val to = token.nextToken().toInt()

        adjacencyList[from].add(to)
        adjacencyList[to].add(from)
    }

    queue.add(1)
    visitedArr[1] = true

    while (queue.isNotEmpty()){
        val from = queue.removeFirst()

        for(to in adjacencyList[from]){
            if(!visitedArr[to]){
                count++
                visitedArr[to] = true
                queue.add(to)
            }
        }
    }

    bw.write(count.toString())
    bw.flush()
    bw.close()
    br.close()
}