743 네트워크 딜레이 타임
743 Network Delay Time
문제
You are given a network of n nodes, labeled from 1 to n.
You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where uiisthe source node,viis the target node, andwiis the time it takes for a signal to travel from source to target.
We will send a signal from a given node k.
Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return-1.
- times[i][0] = ui = 시작 노드
- times[i][1] = vi = 타겟 노드
- times[i][2] = wi = 소요 시간
- k: 시작 노드
- n: 노드의 수
- -1: 불가능할 경우
조건
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n
- ui != vi
- 0 <= wi <= 100
- All the pairs (ui, vi) are unique. (i.e., no multiple edges.)
예제
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
해결
1st
1 생각
- 방향이 있는 그래프.
- 연결이 안 되어 있을 수도 있다
- 연결되어 있어도 방향이 안 맞을 수 있다
- 모든 노드에 도달할 수 있어야 한다
- k에서 시작해서 연결된 노드들에서 신호를 받을 수 있는 시간
- 총합? 은 아니고
- 도달할 수 있는 노드까지의 최단 시간을 구하면 된다
- [[2,1,1],[2,3,1],[3,4,1]]에서, 2에서 시작하면 그 다음 1, 3으로 갈 수 있고, 3에서는 다시 4로 갈 수 있다
1 코드
def first(self, times: List[List[int]], n: int, k: int) -> int:
result = [None] * n
# k를 찾는다
loop_cnt = 0
queue = [k]
while queue and loop_cnt < n:
node_curr = queue.pop(0)
for node in times:
if node[0] == node_curr:
queue.append(node[1])
if result[loop_cnt]:
result[loop_cnt].append(node[2])
else:
result[loop_cnt] = [node[2]]
loop_cnt += 1
ans = 0
print(result)
for values in result:
if values is not None:
ans += max(values)
if ans == 0:
return -1
else:
return ans
1 결과: 실패
times=[
[1, 2, 1],
[2, 1, 3]
]
print(s.first(times, 2, 2)) # Expected: 3
- 처음 2 -> 1에서 모든 노드에 대한 시그널 전파 완료됐으므로, 결과는 3이어야 한다
- 하지만 1 코드에서는 2 -> 1, 1 -> 2까지 카운트 하므로 4가 나오면서 실패
times=[
[1,2,1],
[2,3,2],
[1,3,4]
]
print(s.first(times, 3, 1)) # Expected: 3
2nd
2 생각
- 방문했는지 여부를 체크하면 되지 않을까?
다익스트라?
def Dijkstra(Graph, source):
dist[source] = 0
# create vertex priotiry queue Q
Q = []
for v in Graph:
if v != source:
dist[v] = INFINITY
prev[v] = UNDEFINED
Q.add_with_priority(v, dist[v])
while Q:
u = Q.extract_min()
for neighbor in u:
alt = dist[u] + length(u, neighbor) # `u`까지의 거리에 `u`와 `v` 간의 거리를 더한다
if alt < dist[neighbor]: # 새로 구한 값이 기존 인접 노드까지의 거리보다 작다면
# 값과 이전 노드를 바꾼다
dist[neighbor] = alt
prev[neighbor] = u
Q.decrease_priority(neighbor, alt)
heapq?
2 코드
from typing import *
def second(self, times: List[List[int]], n: int, k: int) -> int:
graph = {}
# 인접 리스트 생성
for node, node_next, time in times:
# 소요 시간을 계속 추적해야 하므로, tuple로 관리
if node in graph:
graph[node].append((node_next, time))
else:
graph[node] = [(node_next, time)]
# print(graph)
loop_cnt = 0
# 인접한 노드들을 탐색하기 위한 큐
# (k까지, 소요되는 시간) 튜플로 저장
queue = [(k, 0)]
# ~까지의 시간을 저장하기 위한 딕셔너리
time_to = {k:0} # 시작 지점의 시간은 처음에 셋팅해 둔다
while queue:
# 현재 정점
node_curr = queue.pop(0)
vertex_curr = node_curr[0]
# 현재 정점 방문 표시
time_accumulative = node_curr[1]
if vertex_curr in graph:
for node_next in graph[vertex_curr]:
# 인접 노드
vertex_next = node_next[0]
# 방문한 적이 있어도, 축적된 값이 더 작으면 그 값으로 치환할 수 있어야 한다
# 그렇다면 "다음 정점이 다시 이전 정점을 가리키면서 무한 반복하는 것 방지"은 어떻게?
time_next = node_next[1]
# 시간을 축적해 간다
time_accumulative_new = time_accumulative + time_next
if vertex_next in time_to:
# 새로 축적된 시간이 기존 시간보다 작으면 더 작은 값으로 바꾼다
if time_accumulative_new < time_to[vertex_next]:
time_to[vertex_next] = time_accumulative_new
# 더 적은 시간이 발견되면 해당 노드 탐색하도록 추가한다
queue.append((vertex_next, time_accumulative_new))
else:
# 새로 축적된 시간없으면 저장
time_to[vertex_next] = time_accumulative_new
# 신규 노드 탐색하도록 추가한다
queue.append((vertex_next, time_accumulative_new))
# print(time_to)
if len(time_to) == n:
return max(time_to.values())
else:
return -1
s = Solution()
case1 = [[2, 1, 1],[2, 3, 1],[3, 4, 1]]
case2 = [[1,2,1],[2,1,3]]
case3 = [[1,2,1],[2,3,2],[1,3,2]]
case4 = [[1,2,1],[2,3,2],[1,3,4]]
case5 = [[3, 1, 5],[3, 2, 2],[2, 1, 2],[3, 4, 1],[4, 5, 1],[5, 6, 1],[6, 7, 1],[7, 8, 1],[8, 1, 1]]
case6 = [[1,2,1],[2,1,3]]
case7 = [[1,2,1],[2,3,7],[1,3,4],[2,1,2]]
print(s.second(case1, 4, 2)) # expected: 2
print(s.second(case3, 3, 1)) # expected: 2
print(s.second(case3, 3, 2)) # expected: -1
print(s.second(case4, 3, 1)) # expected: 3
print(s.second(case5, 8, 3)) # expected: 5
print(s.second(case6, 2, 2)) # expected: 3
print(s.second(case7, 3, 2)) # expected: 6
2 결과: 성공
52 / 52 test cases passed.
Status: Accepted
Runtime: 492 ms
Memory Usage: 16.3 MB
3rd
책의 코드
def answer(self, times: List[List[int]], n: int, k: int) -> int:
graph = collections.defaultdict(list)
"""
그래프 인접 리스트 구성
{
3: [(1, 5), (2, 2), (4, 1)],
2: [(1, 2)],
4: [(5, 1)],
5: [(6, 1)],
6: [(7, 1)],
7: [(8, 1)],
8: [(1, 1)]
}
"""
for u, v, w in times:
graph[u].append((v, w))
# 시작 노드
Q = [(0, k)]
distance = collections.defaultdict(list)
# BFS지만, 최소 힙을 사용하여 시간이 작은 값부터 확인한다
while Q:
# https://docs.python.org/3/library/heapq.html
# time이 가장 작은 원소를 꺼낸다
time, node = heapq.heappop(Q)
print('pop: ', (time, node))
if node not in distance:
# node까지의 거리에 소요되는 시간
distance[node] = time
for v, w in graph[node]:
alt = time + w
print('push: ', (alt, v))
# https://docs.python.org/3/library/heapq.html#basic-examples
# 첫번째 인자 시간(alt)을 최소값으로
heapq.heappush(Q, (alt, v))
print('distance: ', distance)
# 모든 노드 방문했는지 여부 확인
if len(distance) == n:
return max(distance.values())
else:
return -1