[Graph: Dijkstra] 1514. Path with Maximum Probability ★★

1514. Path with Maximum Probability

 

이 문제는 확률 기반 최단 경로 문제로,
다익스트라(Dijkstra) 알고리즘을 확률 최대화 버전으로 변형해서 푸는 문제입니다.
문장을 하나씩 해석하고 → 문제 핵심 → 해결 아이디어까지 차근히 설명드릴게요. 😊

---

📖 한 문장씩 해석

---

You are given an undirected weighted graph of n nodes (0-indexed),
👉 0부터 시작하는 노드 번호를 가진 무방향 가중치 그래프가 주어집니다.
represented by an edge list where edges[i] = [a, b]
👉 간선 목록 edges[i] = [a, b]는 a와 b 노드를 연결하는 무방향 간선을 의미합니다.
with a probability of success of traversing that edge succProb[i].
👉 각 간선을 통과할 성공 확률은 succProb[i]에 주어집니다.
Given two nodes start and end,
👉 시작 노드 start, 도착 노드 end가 주어집니다.
find the path with the maximum probability of success to go from start to end
👉 start에서 end까지 성공 확률이 최대가 되는 경로를 찾으세요.
and return its success probability.
👉 그 경로의 성공 확률을 반환하세요.
If there is no path from start to end, return 0.
👉 만약 start에서 end까지 갈 수 없다면 0을 반환하세요.
Your answer will be accepted if it differs from the correct answer by at most 1e-5.
👉 정답은 오차가 1e-5 이하이면 정답으로 인정됩니다.

💡 문제 핵심 요약

• 그래프는 무방향 + 확률이 간선에 있음
• 경로의 전체 확률 = 경로 상의 간선 확률을 곱한 값
• start → end까지 가능한 경로 중 곱한 확률이 최대인 경로를 찾아야 함
• 갈 수 없으면 0 반환

---

🧠 풀이 전략

✅ 다익스트라 (확률 최대화 버전)

• 다익스트라 알고리즘은 원래 **최단 거리 (min)**를 찾지만,
• 여기서는 **최대 확률 (max)**을 찾아야 하므로 로직을 반대로 써요.

차이점:

• 거리 대신 **확률(prob)**을 저장
• 우선순위 큐는 최댓값 기준이므로 heapq에서 음수값을 넣어서 max-heap처럼 사용

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        # n 노드 0부터 시작
        # edges[i] = [a, b] is an undirected edge connecting the nodes a and b 
        # => 양방향 간선
        # succProb[i]: 가중치
        # start->end 로 가는 성공확률 반환, 반약 없으면 0 리턴
        # 노드 지날때마다 성공확률 누적곱..

        adj = {}
        for i in range(n):
            adj[i] = []

        for (a, b), pr in zip (edges, succProb):
            adj[a].append([pr, b])
            adj[b].append([pr, a])

        maxProb = {} # (pr: 노드별 최대 확률 저장, node: 방문 노드(방문 체크 역할)) 

        # heapq는 기본적으로 minHeap이므로, 확률이 가장 큰 경로를 먼저 처리하기 위해 음수 사용
        # maxheap 이므로 -1 곱해서 넣고, 뺄때도 -1 곱해서..        
        maxHeap = [[-1, start_node]] # Pro, node, 곱해야해서, 초기값은 -1로..
        
        while maxHeap:
            pro, n1 = heapq.heappop(maxHeap)
            pro *= -1

            if n1 in maxProb:
                continue

            maxProb[n1] = pro
            
            """
            [주의 !!]
            for p2, n2 in adj[n1]: O, 현재 노드의 인근노드만 탐색(for p2, n2 in adj[i])해야 함
            for i in range(n): X, 전체 노드를 탐색하면 안됨            
            """
            for p2, n2 in adj[n1]: # 현재 꺼낸 노드의 이웃들을 탐색
                if n2 not in maxProb:                    
                    heapq.heappush(maxHeap, [-1*pro*p2, n2])

        # 도착 노드까지 경로가 없으면 0 반환
        # return 0 if end_node not in maxProb else maxProb[end_node]
        return maxProb.get(end_node, 0)