[백준] 해킹 (10282)(kotlin)

문제 설명

백준 10282번 문제 링크

입력 및 출력

» 입력

• 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다. 각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

» 출력

각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

예제 입출력(테스트케이스)

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

문제 풀이1 (Dijkstra - Adjacency List)

import java.util.PriorityQueue

class Node(val destination: Int, val cost: Int): Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return this.cost - other.cost
    }
}

fun main() = with(System.`in`.bufferedReader()) {
    repeat(readLine().toInt()) {
        val (n, d, c) = readLine().split(" ").map { it.toInt() }
        val adjMatrix = Array(n + 1) { PriorityQueue<Node>() }

        repeat(d) {
            val (a, b, s) = readLine().split(" ").map { it.toInt() }
            adjMatrix[b].add(Node(a, s))
        }

        val result = dijkstra(n, c, adjMatrix)
        val count = result.count { it != Int.MAX_VALUE }
        val time = result
            .map { if (it == Int.MAX_VALUE) 0 else it }
            .maxOf { it }

        println("$count $time")
    }
}

fun dijkstra(n: Int, start: Int, adjMatrix: Array<PriorityQueue<Node>>): IntArray {
    val check = BooleanArray(n + 1)
    val distance = IntArray(n + 1) { Int.MAX_VALUE }
    val q = PriorityQueue<Node>()

    q.add(Node(start, 0))
    distance[start] = 0

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

        if (check[now.destination]) continue
        check[now.destination] = true

        for (next in adjMatrix[now.destination]) {
            if (distance[next.destination] > distance[now.destination] + next.cost) {
                distance[next.destination] = distance[now.destination] + next.cost
                q.add(Node(next.destination, distance[next.destination]))
            }
        }
    }

    return distance
}