04/11 코딩테스트 문제풀이 - 1514. Path with Maximum Probability (Leetcode)

문제

• Leetcode 알고리즘 문제
• 1514. Path with Maximum Probability (Medium)
• 문제 내용 : [링크]
  
  
  
  
  

---

내가 작성한 코드

from collections import defaultdict
class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        probs = [0.0]*n
        graph = defaultdict(list)
        for i, (u,v) in enumerate(edges):
            graph[u].append((v, succProb[i]))
            graph[v].append((u, succProb[i]))

        probs[start_node] = 1.0
        pq = [(-1.0, start_node)]

        while pq:
            cur_prob, cur_v = heappop(pq)

            if cur_v == end_node:
                return -cur_prob

            for next_v, path_prob in graph[cur_v]:
                if -cur_prob * path_prob > probs[next_v]:
                    probs[next_v] = -cur_prob*path_prob
                    heappush(pq, (-probs[next_v], next_v))

        return 0.00000 # end_node 방문 불가능한 경우
          

---

풀이방향

• start_node에서 end_node에 도달하는 가장 높은 확률을 구하는 문제이다.

• 다익스트라 알고리즘을 통해 end_node까지 도달하는 경로 중 가장 높은 확률을 구한다.

---

풀이

• 해당 노드까지 도달하기 위한 가장 높은 확률을 반영하는 probs 리스트를 설정한다.

• graph를 통해 무방향 그래프를 구현한다.

• 첫 출발 start_node의 확률을 1.0으로 설정한다.

• 초기값을 우선순위 큐 pq 에 대입한다.

• 이 때, 가장 높은 확률을 우선으로 탐색하는 다익스트라 알고리즘을 사용해야 하므로, 확률에 마이너스(-)를 붙여 maxheap 구조를 이용한다.

• 아래 과정을 while 문을 통해 반복한다.

  1. 우선순위 큐에서 heappop을 통해 현재 노드까지 도달하는 가장 큰 확률 값 cur_node와 현재 노드 cur_v를 추출한다.

  2. graph[cur_v]에서, 다음 노드(next_v)와 다음 노드까지 가는 확률(path_prob)을 추출한다.

  3. -cur_prob * path_prob 값과 probs[next_v] 값을 비교하여, 큰 값을 probs에 업데이트 해주고, 이 값을 next_v까지 도달하는 최대확률로 반영하여 heappush 해준다.

  4. 위 과정을 cur_v가 end_node가 될 때까지 반복한다.

  5. end_node의 cur_prob 절대값을 return 한다.

• 탐색 이후end_node 방문 경로가 없는 경우, 0.00000을 return 한다.

---

⭐⭐⭐⭐⭐

• 다익스트라 알고리즘을 maxheap과 확률계산 연산으로 응용한 문제이다. 다익스트라 알고리즘의 전형적인 패턴에서 비용/연산을 확률연산으로, 최소값 대신 최대값을 탐색해나가는 문제였다.