[Python] LeetCode 743. Network Delay Time

leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode

다엑스트라 알고리즘 구현이 주목적인 문제.

defaultdict / heapq 자료구조를 활용해 다엑스트라 알고리즘 구현을 해볼 수 있다.

 

이 코드는 아래의 책을 참고해 작성했다.

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기

 

 

	from collections import defaultdict
	import heapq
	class Solution:
	def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
	# 1. 모든 노드가 신호를 받을 수 있는가?
	# 2. 모든 노드에 도달할 때까지의 시간은?
	# = 가장 오래 걸리는 노드까지의 최단거리 = 다엑스트라 알고리즘으로 해결 가능
	# 단방향 = 인접연결리스트로 그래프 정보 구현
	graph = defaultdict(list)
	for _from, _to, time in times:
	graph[_from].append((_to, time))
	# 노드에 도착한 시간을 저장할 dictionary
	arrived = defaultdict(int)
	# [(소요시간, 시작노드)]. 소요시간 기준으로 heapq에서 데이터를 뽑아낸다
	queue = [(0, K)]
	while queue:
	time, node = heapq.heappop(queue)
	if node not in arrived:
	arrived[node] = time
	# 다음으로 이동할 수 있는 노드 탐색
	for _next, delay in graph[node]:
	arrive_time = time + delay
	heapq.heappush(queue, (arrive_time, _next))
	# 1. 모든 노드가 신호를 받았는가
	if len(arrived.keys()) == N:
	# 2. 가장 오래 걸린 노드의 도달값은?
	return max(arrived.values())
	return -1

view raw [Leetcode] Network Delay time.py hosted with ❤ by GitHub