dijkstra(최단거리)_LeetCode_1514 [swift]

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

Path with Maximum Probability - LeetCode

로직 설명: (다른 문제에서 설명함)

접근방법

1. 시작점에서 각node로 갈 최고 확률을 나타내는 dist
2. 다음에 탐색 할 정보를 담고있는 queue
3. 각 노드가 연결된 정보를 나타내는 adjList
4. 위 내용들을 주어진 매개변수로 초기화. dist[시작점] 초기값을 1로 주어, 곱셈에 문제가 없게 함.
5. queue의 첫번째 원소를 꺼내어, 최고 확률과 비교한 뒤, dijkstra 실행

정답코드

class Solution {
        
        var dist : [Double] = []
        var queue : [(Int, Double)] = .init() 
    // {
    //         didSet{
    //             queue.sort() {
    //                 $0.1 < $1.1
    //             }
    //         }
    //     }
        var adjList: [[(Int,Double)]] = []
        
        func maxProbability(_ n: Int, _ edges: [[Int]], _ succProb: [Double], _ start: Int, _ end: Int) -> Double {
            dist = .init(repeating: -1, count: n)
            dist[start] = 1
            
            adjList = .init(repeating: [], count: n)
            
            for(edge, prob) in zip(edges, succProb) {
                
                adjList[edge[0]].append((edge[1],prob))
                adjList[edge[1]].append((edge[0],prob))
            }
            queue.append((start,1))
            
            while !queue.isEmpty {
                let first = queue.removeFirst()
                
                if dist[first.0] > first.1 {
                    continue
                }
                
                dijkstra(start: first.0)
                    
            }
            
            if dist[end] == -1 {
                return 0
            }
            
            return dist[end]
        }
        
        func dijkstra(start: Int) {
            
            for info in adjList[start] {
                if dist[info.0] < 0 ||
                    dist[info.0] < dist[start] * info.1 {
                    dist[info.0] = dist[start] * info.1
                    queue.append((info.0, dist[info.0]))
                }
            }
            
        }
}

 

성적

Runtime: 836 ms, faster than 85.71% of Swift online submissions for Path with Maximum Probability.

Memory Usage: 18.1 MB, less than 100.00% of Swift online submissions for Path with Maximum Probability.