백준 - 2606 바이러스 (코틀린)

[문제]

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

2606번: 바이러스

[풀이]

1번이 속한 연결성분의 정점 수를 구하면 된다.

바이러스에 감염된 컴퓨터 수이기 때문에 1번 컴퓨터를 정점수에서 빼주거나 애초에 더하지 않는 식으로 계산한다.

입력받을 때 각 인덱스마다의 연결리스트를 채워주고 bfs를 이용해서 1번 정점에서 출발하여 탐색을 하면서 갯수를 누적합산하여 구할 수 있다.

시간복잡도 : 연결리스트를 이용한 bfs의 시간복잡도는 O(V+E)이므로 문제에서도 최대 O(V+E)이다. V는 정점의 수 E는 간선의 수이다.

[코드]

import java.util.*

private var n = 0
private var m = 0
private lateinit var computers : Array<ArrayList<Int>>
private lateinit var visited : BooleanArray
private var cnt = 0
fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    n = br.readLine().toInt()
    m = br.readLine().toInt()

    computers = Array(n+1){ arrayListOf()}
    visited = BooleanArray(n+1)

    repeat(m){
        val (first, second) = br.readLine().split(" ").map { it.toInt() }
        computers[first].add(second)
        computers[second].add(first)
    }
    bfs()
    bw.write(cnt.toString())
    bw.flush()
    bw.close()

}
private fun bfs(){
    val queue : Queue<Int> = ArrayDeque()
    queue.add(1)
    visited[1] = true
    while(queue.isNotEmpty()){
        val q = queue.poll()
        for(computer in computers[q]){
            if(visited[computer]) continue
            queue.add(computer)
            visited[computer] = true
            cnt += 1
        }
    }
}