Network Delay Time

Q: Network Delay Time의 시간 복잡도는 얼마인가요?

Dijkstra 알고리즘과 이진 힙을 사용하면 O(E log E)이며, 여기서 E는 링크의 개수입니다. E는 최대 n²이므로 이는 O(E log n)과 같습니다. 인접 리스트, 시간 정보, 힙은 O(n + E)의 공간을 차지합니다. Bellman-Ford는 O(n · E)의 시간과 O(n)의 공간을 사용합니다.

Q: Dijkstra 알고리즘에는 왜 음수가 아닌 가중치가 필요할까요?

Dijkstra는 잠정 시간이 가장 작은 노드를 확정한 뒤 다시는 살펴보지 않습니다. 나중에 더 짧은 경로가 나올 수 없어야만 이 방식이 안전하며, 가중치가 음수가 아니면 미확정 노드를 거치는 모든 경로의 비용은 해당 노드의 시간 이상입니다. 음수 간선은 이 논리를 깨뜨립니다. 더 비용이 많이 드는 것처럼 보였던 노드를 거치는 경로가 결국 더 저렴해질 수 있습니다. 음수 가중치에는 Bellman-Ford를 사용하세요.

Q: Network Delay Time에 BFS를 사용하지 않는 이유는 무엇인가요?

BFS는 시작점에서 몇 개의 링크를 거쳐야 하는지에 따라 노드를 방문하며, 이는 모든 링크에 걸리는 시간이 같을 때만 도착 시간과 일치합니다. 여기서는 링크마다 걸리는 시간이 다르므로, 링크를 더 많이 거치는 경로가 더 빨리 도착할 수도 있습니다. 모든 시간이 같다면 BFS만으로 충분하고, 시간이 0과 1뿐이라면 덱 기반 0-1 BFS가 작동합니다.

Q: 힙 없이 네트워크 지연 시간을 구할 수 있나요?

네. 일반 배열을 사용하는 Dijkstra는 아직 확정되지 않은 모든 노드를 살펴 가장 작은 시간을 찾으므로, 전체 비용이 O(n²)이고 힙이 필요하지 않습니다. E가 n²에 가까운 밀집 그래프에서는 이 방법이 더 나은 선택입니다. 여기의 대규모 테스트처럼 노드가 3,000개이고 링크가 4,000개인 희소 그래프에서는 힙 버전이 훨씬 적은 작업을 수행합니다.

보통최단 경로 그래프 힙

+10

네트워크에는 n개의 노드가 있으며, 노드에는 1부터 n까지 번호가 매겨져 있습니다. 링크는 times라는 목록으로 주어지며, times[i] = [u, v, w]는 노드 u에서 보낸 신호가 w시간 단위 후에 노드 v에 도달한다는 뜻입니다. 링크는 한 방향으로만 작동합니다.

시간 0에 노드 k에서 신호가 출발해 이동할 수 있는 모든 링크를 따라갑니다. 마지막 노드가 신호를 받는 시간을 반환하고, 어떤 노드가 신호를 받지 못하면 -1을 반환하세요.

함수

networkDelayTime(times: integer-2d-array, n: integer, k: integer) → integer

timesinteger-2d-array: 방향이 있는 각 링크는 [u, v, w]로 표시됩니다.
ninteger: 노드의 수
kinteger: 신호를 보내는 노드
반환값integer: 마지막 노드가 신호를 받는 시간 또는 -1

제약 조건

2 ≤ n ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n 그리고 u ≠ v
0 ≤ w ≤ 100
같은 u와 v를 모두 공유하는 링크는 두 개 이상 없습니다.
1 ≤ k ≤ n

예제

입력: times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
출력: 4
설명: 노드 3은 시간 1에 신호를 듣습니다. 노드 2는 직접 연결을 통해 시간 4에 신호를 들을 수 있지만, 노드 3을 거치는 경로로는 1 + 2 = 3에 도착하고, 노드 4는 3 + 1 = 4에 신호를 듣습니다. 노드 4가 마지막으로, 시간 4에 신호를 듣습니다.

제출 시 숨은 테스트 +16개

후속 질문

신호가 m개의 링크를 지난 뒤 약해진다고 가정해 보세요. 그 제한 내에서 마지막 노드가 신호를 듣는 시간을 어떻게 구할까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

각 노드는 k에서 가장 빠른 경로의 길이만큼 시간이 지나면 신호를 받으므로, 이 작업은 방향 그래프에서 단일 출발점 최단 경로를 구한 다음 최댓값을 찾는 것입니다. 답은 가장 큰 최단 시간이며, 어떤 노드에도 경로가 없으면 -1입니다. 링크 시간은 음수가 아니므로, 다익스트라 알고리즘은 최소 힙을 사용해 도착 순서대로 각 노드를 한 번씩 확정할 수 있습니다. 아래에서 E는 링크 수인 times.length입니다.

더 빠른 경로를 찾을 때마다 다시 방문하는 깊이 우선 탐색

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

노드 k에서 시간 0으로 탐색을 시작하고 모든 링크를 따라가며 지금까지의 시간을 함께 전달합니다. 각 노드에 대해 지금까지 확인한 가장 빠른 도착 시간을 기록합니다. 탐색이 기록된 시간보다 빠르지 않게 노드에 도달하면 거기서 멈춥니다. 그 경로가 이후에 제공할 수 있는 것은 이미 더 빠른 경로가 제공했기 때문입니다. 더 빠르게 노드에 도달하면 기록이 갱신되고, 해당 노드 뒤의 모든 경로도 더 빨라질 수 있으므로 탐색은 그 노드에서 계속 진행됩니다.

이는 항상 올바릅니다. 어떤 기록도 갱신하는 경로가 없을 때만 탐색이 멈추며, 각 노드로 가는 최단 경로는 언젠가 그 노드의 기록을 갱신하므로 모든 기록은 결국 실제 최단 시간에 도달합니다.

문제는 노드의 기록이 몇 번이나 갱신될 수 있느냐입니다. 깊이 우선 탐색은 처음 만나는 링크를 따라 끝까지 내려가므로, 느린 경로로 노드에 도달한 뒤 조금 더 빠른 경로로, 그리고 다시 더 빠른 경로로 도달할 수 있으며, 매번 그 노드 뒤의 모든 경로를 탐색합니다. 게이트 18개가 줄지어 있다고 상상해 보세요. 각 게이트 쌍 사이에는 시간이 들지 않는 링크나 우회 경로를 택할 수 있는데, 우회 경로는 링크들이 이어진 경로이며 각 링크의 시간이 합쳐져 65,536, 32,768 등으로 시작해 1까지 내려갑니다. 우회 경로를 먼저 시도하면 탐색은 마지막 게이트에 131,072가지 서로 다른 시간으로 도달하고, 그 시간은 매번 이전보다 빠릅니다. 또한 그 뒤에 있는 노드 1,700개를 매번 탐색하므로 약 2억 2천만 단계가 소요됩니다. 대형 테스트 두 개는 이런 방식으로 만들어졌습니다. 하나는 각 우회 경로를 시간이 들지 않는 링크보다 먼저 나열하고, 다른 하나는 나중에 나열합니다. 따라서 링크를 어떤 순서로 시도하든 탐색은 두 테스트 중 하나에서 문제에 부딪힙니다.

알고리즘

인접 리스트를 만듭니다. 각 노드마다 해당 노드에서 나가는 링크와 그 시간을 기록합니다.
모든 노드의 최적 시간을 무한대로 설정하고 스택에 (k, 0)을 넣습니다.
(node, t)를 꺼냅니다. t가 best[node]보다 작지 않으면 건너뜁니다. 그렇지 않으면 best[node] = t로 설정합니다.
node에서 나가는 각 링크 중 도착 시간이 best[next]보다 빠른 링크에 대해 (next, t + w)를 넣습니다.
스택이 비면, 최적 시간 중 여전히 무한대인 값이 있으면 -1을 반환하고, 그렇지 않으면 가장 큰 값을 반환합니다.

def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    INF = float("inf")
    best = [INF] * (n + 1)  # the fastest arrival found so far at each node
    stack = [(k, 0)]
    while stack:
        node, t = stack.pop()
        # A route that is not faster than one already found adds nothing.
        if t >= best[node]:
            continue
        best[node] = t
        # Push in reverse so the first listed edge is explored first.
        for nxt, w in reversed(graph[node]):
            if t + w < best[nxt]:
                stack.append((nxt, t + w))
    worst = 0
    for node in range(1, n + 1):
        if best[node] == INF:
            return -1
        worst = max(worst, best[node])
    return worst

Bellman-Ford: 모든 간선을 최대 n-1회 완화하기

핵심 아이디어

각 노드에 잠정 시간 dist를 유지합니다. k는 0으로, 나머지는 무한대로 설정합니다. 시간 w인 연결 u → v를 완화한다는 것은 다음을 의미합니다. dist[u] + w가 dist[v]보다 작으면, 해당 연결이 v로 가는 더 빠른 경로를 제공하므로 dist[v]를 그 값으로 낮춥니다. Bellman-Ford는 전체 목록을 여러 번 순회하며 각 순회에서 모든 연결을 완화합니다.

이 과정을 마치면 왜 올바른 시간이 나올까요? 어떤 노드까지 가는 가장 빠른 경로가 k → a → b → v라고 해 봅시다. 첫 번째 순회에서는 dist[k]가 이미 0이므로 k → a를 완화하고, 그 결과 dist[a]가 확정됩니다. 두 번째 순회에서는 dist[b]가 확정되고, 세 번째 순회에서는 dist[v]가 확정됩니다. 순환을 거쳐도 시간이 음수가 되지 않으므로 가장 빠른 경로에서 같은 노드를 두 번 방문할 필요는 없습니다. 따라서 경로에는 최대 n-1개의 연결이 있으며, n-1번의 순회로 모든 노드의 값이 확정됩니다. 아무것도 바뀌지 않는 순회가 있으면 이후 순회에서도 바뀌는 값이 없다는 뜻이므로 그 지점에서 멈춥니다.

각 순회에는 O(E)의 비용이 들므로 최악의 경우 시간 복잡도는 O(n · E)입니다. 목록의 순서에 따라 시간이 얼마나 걸리는지가 달라집니다. 긴 경로의 연결이 먼 쪽부터 시작점 방향으로 나열되어 있으면, 각 순회에서 노드가 하나씩 더 확정됩니다. 큰 테스트 사례 하나가 바로 이런 경우로, 3,000개 노드로 된 사슬이 역순으로 나열되어 있으며, 4,000개의 연결을 2,999번 순회하므로 완화 작업은 약 1,200만 번입니다. 이 크기에서는 여전히 제한 시간 안에 실행되지만, 작업량은 n과 E의 곱에 따라 증가합니다. Bellman-Ford의 강점은 다른 곳에 있습니다. 일부 연결의 시간이 음수여도 올바르게 작동하는데, 이 경우 Dijkstra는 실패합니다.

알고리즘

dist[k] = 0으로 설정하고, 나머지 모든 dist는 무한대로 설정합니다.
최대 n-1회 반복합니다. 각 링크 [u, v, w]에 대해 dist[u] + w < dist[v]이면 dist[v] = dist[u] + w로 설정합니다.
아무것도 변경되지 않은 단계가 끝나면 조기에 중단합니다.
dist 중 무한대인 값이 하나라도 있으면 -1을 반환하고, 그렇지 않으면 가장 큰 값을 반환합니다.

def networkDelayTime(times, n, k):
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    # A fastest route visits each node at most once, so it has at most n-1 edges,
    # and n-1 passes over every edge are enough to find it.
    for _ in range(n - 1):
        changed = False
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:  # a pass that improves nothing means every time is final
            break
    worst = 0
    for node in range(1, n + 1):
        if dist[node] == INF:
            return -1
        worst = max(worst, dist[node])
    return worst

최소 힙을 사용하는 다익스트라 알고리즘

핵심 아이디어

Bellman-Ford는 도착 시간이 아직 확정되지 않은 노드에서 나가는 링크를 완화하고 나중에 다시 처리해야 하므로 여러 번의 순회가 낭비됩니다. Dijkstra 알고리즘은 각 노드의 도착 시간이 확정되는 순간 해당 노드의 링크를 정확히 한 번 완화합니다. 문제는 언제 그 시간이 확정되는지 어떻게 알 수 있느냐는 것입니다.

답은 탐욕 규칙입니다. 아직 확정되지 않은 노드 중 잠정 도착 시간이 가장 작은 노드는 이미 최종 도착 시간이 확정된 상태입니다. 그 노드로 가는 다른 경로는 어느 시점에 확정된 노드들을 떠나야 하며, 확정되지 않은 노드를 거쳐야 합니다. 그 노드의 도착 시간은 적어도 해당 노드의 도착 시간만큼이고, 그 이후의 링크는 음수가 없으므로 도착 시간만 더할 수 있습니다. 따라서 해당 노드의 도착 시간을 확정하고, 링크를 완화한 다음 반복합니다. 첫 번째 예에서는 노드 1의 도착 시간이 0으로 확정되고 노드 2에는 도착 시간 4를, 노드 3에는 도착 시간 1을 제공합니다. 노드 3의 값이 가장 작으므로 도착 시간이 1로 확정되고, 노드 2의 도착 시간을 3으로 낮춥니다. 노드 2의 도착 시간이 3으로 확정되고 도착 시간 4인 노드 4를 찾습니다. 노드 4의 도착 시간이 마지막으로 확정됩니다. 답은 4입니다.

최소 힙을 사용하면 잠정 도착 시간이 가장 작은 값을 빠르게 찾을 수 있습니다. 노드의 도착 시간이 개선될 때마다 (time, node)를 푸시하고, 힙에서 해당 항목을 찾아 제거하는 대신 이전 항목을 힙에 그대로 둡니다. 나중에 이전 항목이 나왔을 때 그 도착 시간은 노드의 현재 도착 시간보다 크므로 건너뜁니다. 각 링크는 항목을 최대 한 번 푸시하므로 힙에는 E + 1개를 초과하는 항목이 들어가지 않으며, 각 푸시 또는 팝의 비용은 O(log E)입니다. 따라서 전체 시간 복잡도는 O(E log E)이고, 인접 리스트와 도착 시간, 힙에 O(n + E) 공간이 필요합니다.

탐욕 규칙이 안전하게 성립하는 것은 도착 시간이 음수가 아니기 때문입니다. 시간이 2인 링크 A → B, 시간이 3인 링크 A → C, 시간이 -2인 링크 C → B를 생각해 봅시다. Dijkstra는 도착 시간이 2일 때 B를 확정하지만, C를 거치는 경로를 이용하면 도착 시간은 1입니다. 신호는 보낸 시점보다 먼저 도착할 수 없으므로 여기서 모든 도착 시간은 0 이상이며, 따라서 규칙이 성립합니다.

알고리즘

모든 노드에 대해 (next, w) 쌍으로 인접 리스트를 만듭니다.
dist[k] = 0으로 설정하고, 나머지 모든 dist는 무한대로 설정한 다음, 최소 힙에 (0, k)를 넣습니다.
가장 작은 (t, node)를 꺼냅니다. t > dist[node]이면 오래된 항목이므로 건너뜁니다.
그렇지 않으면 t가 확정됩니다. node에서 next로 가는 각 연결의 시간이 w일 때, t + w < dist[next]이면 dist[next] = t + w로 설정하고 (t + w, next)를 넣습니다.
힙이 비면, dist 중 무한대인 값이 하나라도 있으면 -1을 반환하고, 그렇지 않으면 가장 큰 값을 반환합니다.

import heapq


def networkDelayTime(times, n, k):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    heap = [(0, k)]  # (arrival time, node), smallest time on top
    while heap:
        t, node = heapq.heappop(heap)
        # A stale entry: this node was already reached sooner.
        if t > dist[node]:
            continue
        # t is now final: every other route reaches node later.
        for nxt, w in graph[node]:
            if t + w < dist[nxt]:
                dist[nxt] = t + w
                heapq.heappush(heap, (t + w, nxt))
    worst = 0
    for node in range(1, n + 1):
        if dist[node] == INF:
            return -1
        worst = max(worst, dist[node])
    return worst

함정과 경계 사례

대부분의 버그는 링크의 방향을 무시하거나, 노드에 처음 제안된 시간을 신뢰하거나, 신호가 도달하지 못한 노드를 추적하지 못하는 데서 발생합니다.

링크를 양방향으로 취급하기. [3, 1, 2]는 신호를 3에서 1로만 전달하므로, 두 번째 예시에서 노드 3은 신호를 받지 못합니다.
일반적인 너비 우선 탐색을 사용하기. 너비 우선 탐색은 가장 빠른 경로가 아니라 링크 수가 가장 적은 경로를 찾습니다. 첫 번째 예시에서는 노드 2에 노드 3을 거쳐 가는 시간 3 대신 직접 링크를 통한 시간 4를 할당합니다.
노드를 꺼낼 때가 아니라 넣을 때 최종으로 표시하기. 노드에 처음 제안된 시간이 항상 최선인 것은 아닙니다. 힙에서 꺼낸 항목 중 가장 작은 항목만 최종 시간입니다.
-1을 잊기. 확인 없이 최댓값을 구하면 무한대를 반환하거나 유한 시간 중 가장 큰 값을 보고하여 신호를 받지 못한 노드를 감춥니다.
노드를 0부터 세기. 노드에는 1부터 n까지 레이블이 붙으므로 배열 크기를 n+1로 설정하고, 사용하지 않는 0번 슬롯은 최댓값을 구할 때 제외합니다.
무한대로 인한 오버플로. 무한대가 가장 큰 int라면, 도달하지 못한 u에 대해 dist[u] + w가 음수로 오버플로됩니다. 도달하지 못한 노드는 건너뛰거나, 여유가 있도록 10^9와 같은 값을 사용하세요.

자주 묻는 질문4

Network Delay Time의 시간 복잡도는 얼마인가요?

Dijkstra 알고리즘과 이진 힙을 사용하면 O(E log E)이며, 여기서 E는 링크의 개수입니다. E는 최대 n²이므로 이는 O(E log n)과 같습니다. 인접 리스트, 시간 정보, 힙은 O(n + E)의 공간을 차지합니다. Bellman-Ford는 O(n · E)의 시간과 O(n)의 공간을 사용합니다.

Dijkstra 알고리즘에는 왜 음수가 아닌 가중치가 필요할까요?

Dijkstra는 잠정 시간이 가장 작은 노드를 확정한 뒤 다시는 살펴보지 않습니다. 나중에 더 짧은 경로가 나올 수 없어야만 이 방식이 안전하며, 가중치가 음수가 아니면 미확정 노드를 거치는 모든 경로의 비용은 해당 노드의 시간 이상입니다. 음수 간선은 이 논리를 깨뜨립니다. 더 비용이 많이 드는 것처럼 보였던 노드를 거치는 경로가 결국 더 저렴해질 수 있습니다. 음수 가중치에는 Bellman-Ford를 사용하세요.

Network Delay Time에 BFS를 사용하지 않는 이유는 무엇인가요?

BFS는 시작점에서 몇 개의 링크를 거쳐야 하는지에 따라 노드를 방문하며, 이는 모든 링크에 걸리는 시간이 같을 때만 도착 시간과 일치합니다. 여기서는 링크마다 걸리는 시간이 다르므로, 링크를 더 많이 거치는 경로가 더 빨리 도착할 수도 있습니다. 모든 시간이 같다면 BFS만으로 충분하고, 시간이 0과 1뿐이라면 덱 기반 0-1 BFS가 작동합니다.

힙 없이 네트워크 지연 시간을 구할 수 있나요?

네. 일반 배열을 사용하는 Dijkstra는 아직 확정되지 않은 모든 노드를 살펴 가장 작은 시간을 찾으므로, 전체 비용이 O(n²)이고 힙이 필요하지 않습니다. E가 n²에 가까운 밀집 그래프에서는 이 방법이 더 나은 선택입니다. 여기의 대규모 테스트처럼 노드가 3,000개이고 링크가 4,000개인 희소 그래프에서는 힙 버전이 훨씬 적은 작업을 수행합니다.

Python

def networkDelayTime(times, n, k):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]
n = 4
k = 1

기대값

Network Delay Time

함수

제약 조건

예제

힌트

풀이

더 빠른 경로를 찾을 때마다 다시 방문하는 깊이 우선 탐색

Bellman-Ford: 모든 간선을 최대 n-1회 완화하기

최소 힙을 사용하는 다익스트라 알고리즘

함정과 경계 사례

자주 묻는 질문4

비슷한 문제