[백준/BOJ] 1082번: 해킹

문제

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

10282번: 해킹

해설

한 컴퓨터가 해킹당했고, 이 컴퓨터에 의존하는 컴퓨터들은 시간이 지남에 따라 전염되기 시작한다.

즉, 한 개의 루트 노드로부터 연결된 노드들이 전부 감염된다는 것이다.

이를 풀기 위해 다익스트라 알고리즘을 응용하였다.

 

다익스트라 알고리즘은 최단 경로를 찾는 알고리즘으로 PriorityQueue를 이용하여 수행해나간다.

하지만 이 문제에서 a, b는 두 번 이상 주어지지 않는다. 즉, 최단 경로라고 할 것이 없다는 것이다.

따라서 나는 Queue를 이용하였다.

 

알고리즘의 수행이 끝나고 나면, 각 컴퓨터에 도달하는 시간들이 전부 구해졌을 것이다.

이때, 초기에 설정해둔 값(Int.MAX_VALUE)이라면 이 컴퓨터는 해킹된 컴퓨터에 의존하지 않는다는 것이다.

초기에 설정해둔 값이 아니라면 해킹된 컴퓨터에 의존하고 있는 것이므로 갯수를 세주고, 이 중 가장 큰 값을 갖고 있는 컴푸터가 모든 컴퓨터가 감염되기까지 걸린 시간을 갖고 있다.

코드

import java.util.*
import kotlin.collections.ArrayList
import kotlin.math.max

private lateinit var graph: Array<ArrayList<Pair<Int, Int>>>
private lateinit var runningTime: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()
    repeat(testCase) {
        val (computerCnt, dependenceCnt, virusComputer) = readLine().split(" ").map { it.toInt() }

        graph = Array(computerCnt + 1) { ArrayList() }
        runningTime = IntArray(computerCnt + 1) { Int.MAX_VALUE }

        repeat(dependenceCnt) {
            val (aComputer, bComputer, time) = readLine().split(" ").map { it.toInt() }
            graph[bComputer].add(Pair(aComputer, time))
        }

        dijkstra(virusComputer)

        var virus = 0
        var totalTime = 0
        for(i in 1 .. computerCnt) {
            if(runningTime[i] != Int.MAX_VALUE) {
                virus++
                totalTime = max(totalTime, runningTime[i])
            }
        }

        println("$virus $totalTime")
    }
}

private fun dijkstra(virusComputer: Int) {
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(virusComputer, 0))
    runningTime[virusComputer] = 0

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curComputer = cur.first
        val curTime = cur.second

        for(i in graph[curComputer].indices) {
            val nextComputer = graph[curComputer][i].first
            val nextTime = curTime + graph[curComputer][i].second

            if(nextTime < runningTime[nextComputer]) {
                runningTime[nextComputer] = nextTime
                que.add(Pair(nextComputer, nextTime))
            }
        }
    }
}