Daily LeetCode Challenge - 743. Network Delay Time

Problem From.
https://leetcode.com/problems/network-delay-time/

이 문제는 다익스트라 알고리즘을 연습해보고 싶어서 푼 문제입니다.
다익스트라 알고리즘은 가중치가 양수인 간선만이 존재할때, 하나의 정점에서 다른 정점으로 가는 최단거리를 계산할 수 있게 해주는 알고리즘.

먼저 각 노드에 대한 정보를 저장할 수 있는 timesMap 을 선언하여,
key 를 각 노드의 번호, value 를 Pair(다음 노드의 번호, 다음 노드까지 가는 가중치) 로 만들어줌.
distance map 을 만들어서 모든 노드 번호를 key 로 넣고 각 value 를 Int.MAX_VALUE 로 만듦
priority queue 로 각 노드의 Pair 두번째 value 가 작은 순서대로 우선순위를 가질 수 있도록, 만들어서 각 노드에서 다음 탐색할 노드가 최소의 거리를 가진 노드가 먼저 나올수 있도록 정보를 넣어둠
priority queue 를 만든 이유는, 그냥 구현하게 되면 O(N^2) 의 시간 복잡도를 가지는 알고리즘이 우선순위 queue 를 사용하게 되면, 처음부터 다 탐색할 필요가 없기 때문에 O(NlogN) 의 시간복잡도를 가질 수 있기 때문입니다.

이제 필요한 자료구조는 모두 선언했으니 priority queue 에 노드를 넣고, 방문하지 않은 노드를 찾으면서 각 노드에서 다음 노드로 갈때, distance map 에 (현재 노드까지의 거리 + 다음 노드까지의 거리) 값이 최솟값을 가질 수 있도록 Math.min 을 통해 갱신해줍니다.

모든 노드를 다 탐색했다면, distance map 을 돌면서 그 값들 중에 가장 큰 수를 찾아냅니다. 여기서 가장 큰 수를 찾아내는 이유는, distance 에는 처음부터 2 -> 1 갔을때의 가중치 2-> 3 갔을때의 가중치 만을 가지는 값도 존재하므로 최솟값으로 찾으면 안돼고, 모든 노드를 다 탐색했다고 가정하면 항상 최솟값이 들어있기 때문에, distance map 에서의 최대값을 찾으면 우리가 필요한 최소거리가 나오게 됩니다.

문제에서 요구한대로 최솟값을 찾으면 그 값을 리턴하고, distance map 에 노드를 미처 다 탐색하지 못해서 Int.MAX_VALUE 가 남아있는 노드가 있다면 -1 을 리턴합니다.

class Solution {
    fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
        
        var answer = Int.MIN_VALUE
        val distance = HashMap<Int, Int>()
        val timesMap = HashMap<Int, ArrayList<Pair<Int, Int>>>()
        val visit = hashSetOf<Int>()
        val priorityQueue = PriorityQueue<Pair<Int, Int>>(compareBy{ it.second })
        
        for(i in 1..n) {
            distance[i] = Int.MAX_VALUE
        }
        
        times.forEach {
            timesMap[it[0]] = timesMap.getOrDefault(it[0], arrayListOf<Pair<Int, Int>>()).apply { add(Pair(it[1], it[2])) }
        }
        
        priorityQueue.add(Pair(k, 0))
        distance[k] = 0
        
        while(priorityQueue.isNotEmpty()) {
            val pair = priorityQueue.poll()
            
            val currNode = pair.first
            val currCost = pair.second
            
            visit.add(currNode)
            
            timesMap.get(currNode)?.forEach {
                val nextNode = it.first
                val nextCost = it.second
                if(!visit.contains(nextNode)) {
                    priorityQueue.add(Pair(nextNode, currCost + nextCost))
                    distance[nextNode] = Math.min(currCost + nextCost, distance[nextNode]!!)
                }
            }
            
        }
        
        distance.forEach {
            answer = Math.max(answer, it.value)
        }
        
        return if(answer == Int.MAX_VALUE) -1 else answer
    }
}