[python3] 1514. Path with Maximum Probability

풀이 일자: 23.06.28

난이도: [Medium]

분류: [Shortest Path/ Bellman-Ford/ Dijkstra]

문제 내용

문제의 내용은 start부터 end까지 간다고 했을 때 가장 높은 weight를 가지고 있는 경로의 weight를 반환하는 문제이다.

 

문제 해결 흐름

1. 우선 하나의 노드에서 다른 노드로의 이동이기 때문에 BFS를 생각해보았다.(실패)

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        visited = list();
        path = dict();

        for i in range(len(edges)):  # 참조하기 쉽도록 path를 만들어주고
            if edges[i][0] not in path:
                path[edges[i][0]]= list();
            path[edges[i][0]].append([edges[i][1], succProb[i]]);

            if edges[i][1] not in path:
                path[edges[i][1]]=list();
            path[edges[i][1]].append([edges[i][0], succProb[i]]);

        if start not in path or end not in path: # 시작점과 끝점이 path에 없다면 이어지지 않은 것이므로 0 리턴
            return 0;

        visited.append(start);
        q = deque();

        for nxt in path[start]: # 시작점 기준으로 주위 노드들을 다 넣고
            q.appendleft(nxt);

        ans = 0;
        while q:
            node, prop = q.pop();
            if node == end:
                ans = max(ans, prop);
            else:
                visited.append(node);
                for nxt in path[node]: # 주변 노드들과 지금까지의 prop을 곱해줌.
                    if nxt[0] not in visited:
                        q.appendleft([nxt[0],prop*nxt[1]]);
        
        return ans;

결과는 실패였다. Solution을 확인해보니 나는 visited를 통해 한번 지나가면 끝으로 처리했는데 다른 route를 통해서 현재 route에서 지나간 노드를 지나갈 수 있다고 생각했어야 했다.

=> 즉 내 코드에서 방문여부를 확인하는 것 대신 현재 노드에서 다음 노드로 이동했을 때의 prob과 다음 노드의 최대 prob를 비교했어야 한다.

 

다른 해결 방식

1. weight가 뭐가 나오든 상관없이 최단거리를 구할 수 있는 알고리즘인 Bellman-Ford 알고리즘(Official Sol)

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        max_prob = [0] * n
        max_prob[start] = 1 # start부분을 prob를 1로 두고 이를 기준으로 주변의 prob를 확인하는 형태
        
        for i in range(n - 1): # 최대 n-1개의 이동이 존재할 수 있음.
            has_update = 0
            for j in range(len(edges)):
                u, v = edges[j]
                path_prob = succProb[j] # u에서 v로 가는 것과 v에서 u로 가는 것에 대해 최대 prob를 넣어줌.
                if max_prob[u] * path_prob > max_prob[v]:
                    max_prob[v] = max_prob[u] * path_prob
                    has_update = 1 
                if max_prob[v] * path_prob > max_prob[u]:
                    max_prob[u] = max_prob[v] * path_prob
                    has_update = 1
            if not has_update: # 더이상의 업데이트가 없다면 끝
                break
        
        return max_prob[end]

 

2. 빠른 최단거리 알고리즘.(Official Sol)

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = defaultdict(list)
        for i, (a, b) in enumerate(edges):
            graph[a].append([b, succProb[i]])
            graph[b].append([a, succProb[i]])
            
        max_prob = [0.0] * n    
        max_prob[start] = 1.0
        
        queue = deque([start]) # Queue에 시작점을 넣고
        while queue:
            cur_node = queue.popleft()
            for nxt_node, path_prob in graph[cur_node]:
                if max_prob[cur_node] * path_prob > max_prob[nxt_node]: # 현재 노드에서 이동하는 것과 다른 방향에서 다음 노드로 이동하는 것 중 max인 것 선택
                    max_prob[nxt_node] = max_prob[cur_node] * path_prob
                    queue.append(nxt_node)
                    
        return max_prob[end]

 

 

3. weight가 음수가 아니니까 굳이 Bellman-Ford를 사용할 필요없이 Dijkstra 알고리즘 사용해도 되겠네.(Official Sol)

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = defaultdict(list)
        for i, (u, v) in enumerate(edges):
            graph[u].append((v, succProb[i]))
            graph[v].append((u, succProb[i]))
        
        max_prob = [0.0] * n
        max_prob[start] = 1.0
        
        pq = [(-1.0, start)]    
        while pq:
            cur_prob, cur_node = heapq.heappop(pq)
            if cur_node == end:
                return -cur_prob
            for nxt_node, path_prob in graph[cur_node]:

                if -cur_prob * path_prob > max_prob[nxt_node]:
                    max_prob[nxt_node] = -cur_prob * path_prob
                    heapq.heappush(pq, (-max_prob[nxt_node], nxt_node))
        return 0.0

 

문제 링크

Path with Maximum Probability - LeetCode