[백준] 바이러스 (2606)(Kotlin)

원본 문제

문제 설명

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

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

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

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

입출력 예제1

입력	출력
7 6 1 2 2 3 1 5 5 2 5 6 4 7	4

입출력 예제2

입력	출력
4 4 4 3 1 3 2 4 2 3	3

문제 풀이1 (BFS)

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

var computers: Int = 0
var matrix: Array<IntArray> = arrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    computers = readLine().toInt()
    matrix = Array(computers) { IntArray(computers) }

    repeat(readLine().toInt()) {
        val connection = readLine()
            .split(" ")
            .map { it.toInt() }

        matrix[connection[0] - 1][connection[1] - 1] = 1
        matrix[connection[1] - 1][connection[0] - 1] = 1
    }

    println(bfs(0) - 1)


}

fun bfs(infected: Int): Int {
    val queue: LinkedList<Int> = LinkedList()
    var status: IntArray = IntArray(computers) { 0 }

    queue.add(infected)

    while (queue.isNotEmpty()) {
        val now = queue.poll()

        if (!matrix[now].contains(1)) continue
        else {
            matrix[now].forEachIndexed { index, value ->
                if (value == 1 && status[index] != 1) {
                    status[index] = 1
                    queue.add(index)
                }
            }
        }
    }

    return status.count { it == 1 }
}

문제 풀이2 (DFS)

import java.io.BufferedReader
import java.io.InputStreamReader

var computers: Int = 0
var matrix: Array<IntArray> = arrayOf()
var visited: BooleanArray = booleanArrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    computers = readLine().toInt()
    matrix = Array(computers) { IntArray(computers) }
    visited = BooleanArray(computers) { false }

    repeat(readLine().toInt()) {
        val connection = readLine()
            .split(" ")
            .map { it.toInt() }

        matrix[connection[0] - 1][connection[1] - 1] = 1
        matrix[connection[1] - 1][connection[0] - 1] = 1
    }

    dfs(0)
    println(visited.count { it } - 1)

}

fun dfs(infected: Int) {

    visited[infected] = true

    for (i in 0 until computers) {
        if (matrix[infected][i] == 1 && !visited[i]) {
            dfs(i)
        }
    }

}

문제 풀이3 (Floyd-Warshall)

import java.io.BufferedReader
import java.io.InputStreamReader

var computers: Int = 0
var matrix: Array<IntArray> = arrayOf()
var visited: BooleanArray = booleanArrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    computers = readLine().toInt()
    matrix = Array(computers) { IntArray(computers) { Int.MAX_VALUE } }
    visited = BooleanArray(computers) { false }

    repeat(readLine().toInt()) {
        val connection = readLine()
            .split(" ")
            .map { it.toInt() }

        matrix[connection[0] - 1][connection[1] - 1] = 1
        matrix[connection[1] - 1][connection[0] - 1] = 1
    }

    for (i in 0 until computers)
        matrix[i][i] = 0

    floydWarshall()
    println(matrix[0].filter { it != 0 && it != Int.MAX_VALUE }.count())

}

fun floydWarshall() {

    for (k in 0 until computers) {
        for (i in 0 until computers) {
            if (matrix[i][k] == Int.MAX_VALUE) continue
            for (j in 0 until computers) {
                if (matrix[k][j] == Int.MAX_VALUE) continue
                matrix[i][j] = Math.min(matrix[i][k] + matrix[k][j], matrix[i][j])
            }
        }
    }

}