1514. Path with Maximum Probability

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

input :

• n, edges, succPro, start, end
• 2 <= n <= 10^4

output :

• start에서 end까지 이동하며 가지는 가장 큰 probability를 출력하시오.

조건 :

• 양방향 그래프를 이루고 있다.

---

Solution explain : Solution

idea

주의

시간 초과가 발생하였다면 조건에 주의하지 않은 것이다.
now_proba가 probaStore[next_node]와 같았다면 이전에 이미 해당 값으로 순회를 하였기에 할 필요가 없다.

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        q = deque([])
        probaStore = [0] * n
        edge = dict()

        for item in range(n):
            edge[item] = []

        for idx, temp in enumerate(edges):
            a, b = temp
            edge[a].append((b, idx))
            edge[b].append((a, idx))

        probaStore[start] = 1
        q.append((start, probaStore[start]))
        while q:
            now_node, proba = q.popleft()

            if now_node == end:
                if proba > probaStore[now_node]:
                    probaStore[now_node] = proba
                    continue

            for next_node, idx in edge[now_node]:
                now_proba = probaStore[now_node] * succProb[idx]
                if now_proba > probaStore[next_node]:
                    probaStore[next_node] = now_proba
                    q.append((next_node, now_proba))
        return probaStore[end]