문제40: 네트워크 딜레이 타임

문제

K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값(u,v,w)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다.

입력


times=[[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2

출력

풀이

다익스트라 알고리즘 구현 → 다음의 2가지 사항을 판별해야 한다.

모든 노드가 신호를 받는 데 걸리는 시간
모든 노드에 도달할 수 있는지 여부


graph = collections.defaultdict(list)
# 그래프 인접리스트 생성
for u,v,w in times:
	graph[u].append((v,w))

# 큐 변수: [(소요시간, 정점)]
Q = [(0, k)]
dist = collecitons.defaultdict(int)

# 우선순위 큐 최솟값 기준으로 정점까지 최단 경로 삽입
while Q:
	time, node = heapq.heappop(Q)
		if node not in dist:
			dist[node] = time
			for v, w in graph[node]:
				alt = time + w
				heapq.heappush(Q, (alt, v))

# 모든 노드의 최단 경로 존재 여부 판별
if len(dist) == N:
	return max(dist.values())
return -1

문제40: 네트워크 딜레이 타임

문제

입력

출력

풀이

새로운 개념