[Kotlin] 백준 2606번 : 바이러스 <Silver 3>

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

2606번: 바이러스

Code

---

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

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val computerCount = readLine().toInt()
    val times = readLine().toInt()

    var graph = Array(computerCount+1, {BooleanArray(computerCount+1,{false})})

    var visited = BooleanArray(computerCount+1, {false})
    visited[1] = true

    repeat(times){
        val (fir, sec) = readLine().split(" ")
        graph[fir.toInt()][sec.toInt()] = true
        graph[sec.toInt()][fir.toInt()] = true
    }

    var starPoint : Queue<Int> = LinkedList()
    starPoint.add(1)

    var cnt = 0
    while (starPoint.isNotEmpty()) {
        var num = starPoint.poll()

        for (i in 1..computerCount) {
            if (graph[num][i] && !visited[i]) {
                cnt++
                visited[i] = true
                starPoint.add(i)
            }
        }
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    bw.write("${cnt}")
    bw.flush()
    bw.close()
}

---

이 문제는 전형적인 Graph 문제다. 

완전탐색 문제이기 때문에 BFS든 DFS든 본인이 더 좋아하는 방식으로 구현하면 된다.

 

입력받는대로 2차원 배열에 표시하고, BFS를 활용해서 탐색을 시작한다.

내가 안가본 곳이라면 방문했다는 기록을 남기고 값을 Queue에 추가하여 BFS를 쭉 이어간다.

 

사실 이거말고는 추가적으로 설명할게 없다. 전형적인 BFS문제였고, Queue에 추가하는 조건 정도만 정하면 되는 문제였다.