백준 10282 해킹 (다익스트라)

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

그래프 구조의 네트워크에서 한 정점부터 연결된 컴퓨터들의 수와 연결된 마지막 컴퓨터까지 전염되는 시간을 구하는 문제이다.

시간은 양수이므로 전염되는 시간을 가중치로 하는 그래프에서 다익스트라 알고리즘을 이용해 입력받은 정점부터 다른 점들까지의 최소 경로를 구하고, 경로가 존재하는 정점들의 수, 연결된 컴퓨터들의 최소 경로중 최댓값을 출력하면 된다.

다익스트라 알고리즘이란?

가중치가 양수인 그래프에서 한 정점부터 다른 정점들까지의 최단 거리를 구하는 알고리즘이다.

방법을 요약하자면 한 점부터 인접한 점들을 하나씩 방문하며 방문한 점을 경유해 다른 점으로 이동했을 때 기존 거리 배열의 값보다 적은 경우 갱신하는 것이다.

간단한 케이스를 통해 예시를 들어보겠다.

1번 정점을 시작점으로 한다고 가정하고 distance 배열을 구성한다.

1	2	3	4
0	INF	INF	INF

시작점인 1은 거리를 0으로 지정하고, priority queue(거리 작은순)에 넣는다.

priority queue: [(1,0)] - (정점, 비용)

다음 반복문으로 queue에서 1을 빼내고, 1과 연결된 정점들로 이동하는 비용이 현재 distance배열보다 작다면 갱신 후 queue에 넣는다.

(2로 이동하는 비용 2는 현재 distance[2]가 INF이므로 이를 2로 바꾸고 2를 queue에 넣는다.
마찬가지로 3에 대해서도, 비용 8이 INF보다 작으므로 갱신 후 넣는다)

priority queue: [(2,2), (3,8)]

1	2	3	4
0	2	8	INF

다음 queue에서 2를 빼내고, 1에서 2로 이동한 후 2와 연결된 정점들로 이동하는 비용이 현재 distance배열보다 작다면 갱신 후 queue에 넣는다.

2에서는 3과 4로 이동할 수 있다.

1에서 2를 거쳐 3으로 이동하는 경우 비용은 2+4=6으로 distance[2]인 8보다 작다. 따라서 distance[2]를 6으로 바꾼 후 3을 비용 6과 함께 queue에 넣는다

1에서 2를 거쳐 4로 이동하는 경우 비용은 2+5=7로 distance[4]인 INF보다 작다. 따라서 distance[4]를 7로 바꾸고 4를 비용 7과 함께 queue에 넣는다.

priority queue: [(3,6), (4,7), (3,8)]

1	2	3	4
0	2	6	7

이후 나머지 값들은 queue에서 뽑아도 연결된 정점이 없어 queue에서 제거되고 반복문이 종료된다.

현재 배열에 담겨 있는 값인 0, 2, 6, 7이 1에서 출발하는 경우 최소 거리들이다.

이 다익스트라 알고리즘을 이용하여 문제의 정답을 구할 수 있다.

각 케이스에 대해서 지정된 출발점부터 최소 거리들의 배열을 얻은 후 거리가 INF가 아닌 점들의 개수가 감염 컴퓨터 개수이고, INF가 아닌 값들 중 최댓값이 모두 감염에 걸리는 시간이 된다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val case = readLine().toInt()

    for(i in 1..case){
        val (n, d, c) = readLine().split(' ').map{it.toInt()}
        val map = Array(n+1){LinkedList<Pair<Int,Int>>()}
        val pq = PriorityQueue<Pair<Int,Int>>{n1, n2 ->
            n1.second - n2.second
        }

        for(j in 1..d){
            val line = readLine().split(' ').map{it.toInt()}

            map[line[1]].add(Pair(line[0],line[2]))
        }

        fun dijkstra(start: Int): IntArray{
            val distances = IntArray(n+1){i -> Int.MAX_VALUE}
            distances[start] = 0
            pq.offer(Pair(start,0))

            while(pq.isNotEmpty()){
                val now = pq.poll()
                if(distances[now.first] < now.second)
                    continue
                for(j in map[now.first]){
                    val cost = now.second + j.second
                    if(distances[j.first] > cost){
                        distances[j.first] = cost
                        pq.offer(Pair(j.first, cost))
                    }
                }
            }
            return distances
        }

        val shortestRoutes = dijkstra(c)
        var ans1 = 0
        var ans2 = 0
        for(s in shortestRoutes){
            if(s != Int.MAX_VALUE && ans2 < s)
                ans2 = s
            if(s != Int.MAX_VALUE)
                ans1++
        }
        println("$ans1 $ans2")
    }
}

컴퓨터 개수(n)가 최대 10000개이므로 연결 리스트 기반 그래프를 구성하였다.

그래프를 입력 받은 후, 다익스트라 알고리즘을 적용해 얻은 출발점(c)부터의 최단 거리들 배열을 통해 정답을 얻어냈다.

다익스트라 알고리즘을 구현할 때, distance배일을 Int.MAX_VALUE로 초기화시키고 알고리즘을 수행한다.

while(큐에 원소가 남는동안){
큐에서 원소 뽑아 뽑은 원소까지 가는 비용이 distance배열보다 크면 넘어감.
작으면 해당 원소와 연결된 정점을 해당 원소를 거쳐 가는 비용과 비교하여 distance를 갱신하고 queue에 넣음.
}