백준 - 2606 바이러스

문제

2606 바이러스

답

kotlin code

fun main() {
    q2606()
}

fun q2606() {
    val input:Network = readNetwork()

    val sickComputers = getSickComputers(input)

    println(sickComputers.count() - 1)
}

fun readNetwork(): Network {
    val computers = Array(readln().toInt()){ i -> i + 1 }.toSet()
    val pairs = Array(readln().toInt()) {
        val ln = readln().split(" ").map { it.toInt() }
        Pair(ln.minOf { it }, ln.maxOf { it })
    }.toSet()

    return Network(computers, pairs)
}

fun getNext(input: Network, nextServer: Int): Set<Pair<Int, Int>> {
    return input.pairs.filter { it.first == nextServer || it.second == nextServer }.toSet()
}

fun getSickComputers(input: Network): MutableSet<Int> {
    val sickComputers = mutableSetOf(1)
    val checkedComputers = mutableSetOf<Int>()

    while(true) {
        val targetComputerList = sickComputers.filter { !checkedComputers.contains(it) }
        if(targetComputerList.isEmpty()) break
        for(targetComputer in targetComputerList) {
            val next = getNext(input, targetComputer)
            for (pair in next) {
                sickComputers.add(pair.first)
                sickComputers.add(pair.second)
            }
            checkedComputers.add(targetComputer)
        }
    }
    return sickComputers
}

data class Network(val computers:Set<Int>, val pairs:Set<Pair<Int, Int>>);