Path with Maximum Probability
https://leetcode.com/problems/path-with-maximum-probability/description/
문제 파악 [필수 작성]
문제이해
start 부터 end까지 가는 동안에
각 weight 들을 곱해서 최대가 되는 weight 를 리턴
만약 갈 수 있는길이 없으면 0 을 리턴
제한 조건 확인
소수점 아래 5자리까지만 표현
n은 최대 10,000개
start 랑 end는 다름
엣지는 최대 2n개
확률은 0~1 사이
아이디어
곱하면 곱할수록 작아질 수 밖에 없음
다익스트라인데 최대값순으로 확장
힙활용해서 구현
방향그래프가 아니기 때문에 서로를 가리키도록
연결리스트를 초기화해주어야함
최대값 순서로 먼저 방문했다고 해서 최댓값을 보장해주지 않음 -> test case 2번에서 [1,2] 사이를 1로 바꾼경우
따라서 만약 최댓값이 업데이트 되면
해당 노드부터 전파를 다시 진행해주어야함
시간복잡도
(V+E)log(V) = 310^4 log (10^3 10) < 310^4 log(2^14)
= 30,000 14 => 시간충분
근데 단순히 각 노드를 한번만 방문하는건 아니여서 다시 생각해봐야함
-> 생각이 어려워서 우선 제출해보았는데 통과되버림...
-> 제출 이전에 내가 시간내에 통과가능하다는걸 검증할 수 있어야함..
-> 생각을 잘못했음
-> 애초에 max_heap 의 특성때문에 weight 가 최대인 노드부터 전파가 시작됨.
즉, 비교를 통해 특정 노드의 weight 값이 계속 바뀔수는 있지만,
해당 노드가 현재 모든 노드중 최대값이 아니면 전파가 시작되지를 않음
-> 만약, 다시 해당 노드로 돌고돌아 도착했는데 값이 더 커진다면?
-> 이는 불가능함. 왜냐하면 weight가 0~1 사이이기때문에 무조건 돌고돌아 돌아오면
같거나 더 작을수밖에 없음. 즉, 이 문제의 알고리즘은 w가 0~1 사이에서만 동작함 1보다 큰
w가 있는경우 무한루프에 빠질 수 있음
-> 따라서 원래 생각했던, 시간복잡도가 맞음
자료구조
힙 : (weight, 다음노드번호)
연결리스트 : [[(weight, 다음노드번호),(weight, 다음노드번호)],. . .]
visited : []
접근 방법 [필수 작성]
코드 구현 [필수 작성]
1차시도 (약 35분 소요)
한방에 통과!!
import heapq
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
link_list = [[] for _ in range(n)]
node_w_list = [-1 for _ in range(n)]
max_heap = []
for i in range(len(edges)):
node_1 = edges[i][0]
node_2 = edges[i][1]
link_list[node_1].append((succProb[i],node_2))
link_list[node_2].append((succProb[i],node_1))
heapq.heappush(max_heap,(-1,start_node))
node_w_list[start_node] = 1
while max_heap:
tw, tn = heapq.heappop(max_heap)
for nw,nn in link_list[tn]:
if node_w_list[nn] < abs(tw)*nw:
node_w_list[nn] = abs(tw)*nw
heapq.heappush(max_heap,(node_w_list[nn]*(-1),nn))
if node_w_list[end_node] == -1:
return 0
else:
return node_w_list[end_node]배우게 된 점 [필수 작성]
10^3 < 2^10 일 뿐만 아니라
10 < 2^4 이니 이것도 생각하자
질문 [ 필수 X ]
제 생각의 흐름이 맞는지 확인 한번 부탁드립니다.
답변
화살표를 통해 작성하신 생각의 흐름은 맞습니다.
우선순위 큐에 동일한 노드가 여러번 삽입되는 경우는 존재하지만 만약 해당 노드가 이미 최대값으로 선정된 노드였다면 다익스트라를 진행함에 따라 해당 노드까지 가는 확률은 더 감소하게 됩니다.
해당 노드가 최대값으로 선정된 적 없는 노드였다면 우선순위가 갱신됨에 따라 이후에 추가된 확률이 더 높은 노드가 먼저 선정될 것이고 이후는 위에 적어둔 내용과 동일하게 작동됩니다.
시간 복잡도는 아래와 같이 계산하는게 편합니다.
