Leetcode 1514. Path with Maximum Probability

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

Path with Maximum Probability - LeetCode

문제

0번 부터 시작하는 n개의 노드는 방향이 없는 가중치가 있는 그래프이다. 주어지는 edges는 edges[i] = [a, b]로 이루어져 있으며 a, b는 각 노드를 뜻하며 이는 a 와 b 사이가 방향이 없는 선이 연결되어 있음을 의미한다. 이 a와 b에 연결된 선으로 여행할 수 있는 확률은 succProb[i]에서 주어진다.

 

주어지는 node인 start와 end를 이용해 start에서 시작해 end까지 가는 길 중 여행할 수 있는 확률이 가장 높은 확률을 반환하여라.

 

만약 start와 end로 이어지는 길이 없다면 0을 반환하라. 또한 정답은 소수점 5째자리까지 비교된다.

 

코드

from collections import deque

class Solution:

    def maxProbability(self, n: int, edges: list[list[int]], succProb: list[float], start: int, end: int) -> float:

        m = [[] for _ in range(n)]

        q = deque([start])

        answer = [0] * n

        answer[start] = 1.0

        for i, (f, t) in enumerate(edges):

            m[t].append((f, succProb[i]))

            m[f].append((t, succProb[i]))

        # print(m)

        while q:

            cursor = q.popleft()

            for next, weight in m[cursor]:

                if weight != 0:

                    new_weight = weight * answer[cursor]

               

                    if new_weight > answer[next]:

                        answer[next] = new_weight

                        q.append(next)

        return answer[end]