https://leetcode.com/problems/path-with-maximum-probability/
input :
output :
조건 :
Solution explain : Solution
시간 초과가 발생하였다면 조건에 주의하지 않은 것이다.
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]