[백준/BOJ] 2606번: 바이러스

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

2606번: 바이러스

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

해설

연결되어 있는 인접 노드(컴퓨터)의 수를 구하는 것이므로 DFS, BFS 어떤 방식을 쓰든 상관없다.

나는 DFS를 이용하여 문제를 풀어보았다.

i번째 컴퓨터를 방문하였는지와 현재 노드와 i번째 컴퓨터가 연결되 있는지를 확인하여 두 조건이 만족한다면 재귀함수를 통해 다른 컴퓨터와의 연결이 있는지를 확인하고, 인접한 노드의 수를 더한다.

1번 컴퓨터는 이미 감염되 있으므로 1을 뺀 값을 출력하도록 한다.

소스 코드

import java.util.*
val computer = readLine()!!.toInt()
val adjacent: Array<Array<Boolean>> = Array(computer) { Array(computer) { false } }
val visit = Array(adjacent.size) { false }

fun main() {
    var st: StringTokenizer
    val connect = readLine()!!.toInt()
    for(i in 0 until connect) {
        st = StringTokenizer(readLine())
        val a = st.nextToken().toInt() - 1
        val b = st.nextToken().toInt() - 1
        adjacent[a][b] = true
        adjacent[b][a] = true
    }
    val result = check(0)
    println(result - 1)
}

fun check(start: Int): Int {
    var cnt = 1
    visit[start] = true
    for(i in adjacent.indices) {
        if(adjacent[start][i] && !visit[i]) cnt += check(i)
    }
    return cnt
}