Daily LeetCode Challenge - 1514. Path with Maximum Probability

Problem From.

https://leetcode.com/problems/path-with-maximum-probability/

오늘 문제는 graph 가 주어졌을때, 각 graph 에서 간선의 값이 probability 라고 할때, start 에서 end 까지 가는 수 중에 가장 확률이 큰 경우를 구하는 문제였다.

가장 확률이 큰 수를 찾는 문제이므로, 먼저 priority queue 를 이용하여, probability 를 기준으로 내림차순으로 원소가 정렬될 수 있도록 queue 를 구현하였다.
그런 다음 노드의 번호와, probability 를 페어로 묶어서, queue 넣어주었다.
마지막으로 queue 에서 start 부터 시작하여, probability 를 계산해주었는데, priority queue 를 이용하였으므로, 항상 queue 에서 꺼내올때마다, 확률이 가장 높은 경우가 나오게 만들어주었다.

class Solution {
    fun maxProbability(n: Int, edges: Array<IntArray>, succProb: DoubleArray, start: Int, end: Int): Double {
        val pq = PriorityQueue<Pair<Int, Double>>(Comparator { p1, p2 -> p2.second.compareTo(p1.second) })
        val visited = HashSet<Int>()
        val adjMap = HashMap<Int, MutableList<Pair<Int, Double>>>()
        
        edges.forEachIndexed { i, edge ->
            adjMap.putIfAbsent(edge[0], mutableListOf<Pair<Int, Double>>())
            adjMap.putIfAbsent(edge[1], mutableListOf<Pair<Int, Double>>())
            adjMap.get(edge[0])?.add(Pair(edge[1], succProb[i]))
            adjMap.get(edge[1])?.add(Pair(edge[0], succProb[i]))
        }
        
        pq.add(Pair(start, 1.0))
        while (pq.size > 0) {
            val pair = pq.poll()
            val curNode = pair.first
            val curProb = pair.second
            if (curNode == end) return curProb
            if (curNode in visited) continue
            visited.add(curNode)
            for (next in adjMap.getOrDefault(curNode, mutableListOf<Pair<Int, Double>>())) {
                val nextProb = curProb * next.second
                pq.add(Pair(next.first, nextProb))
            }
        }
    
        return 0.0
        
    }
}