Network Delay Time

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

다익스트라 알고리즘과 이진 힙을 사용하면 O(E log E) 이며, 여기서 E는 링크의 개수입니다. E는 최대 n²이므로 이는 O(E log n) 과 같습니다. 공간 복잡도는 O(n + E) 입니다. 벨만-포드 알고리즘은 O(n · E) 시간이 걸립니다.

Q: 다익스트라 알고리즘에는 왜 음수가 아닌 가중치가 필요할까요?

Dijkstra는 확정된 노드를 다시 방문하지 않는데, 이는 이후에 더 짧은 경로가 없을 때만 안전합니다. 이동 시간이 2인 A → B , 이동 시간이 3인 A → C , 이동 시간이 -2인 C → B 링크가 있으면, B 를 2로 확정하지만 C 를 거치는 경로로는 1에 도달합니다. Bellman-Ford는 음수 이동 시간을 처리합니다.

Q: 힙 없이 네트워크 지연 시간 문제를 풀 수 있나요?

네. 일반 배열을 사용하는 다익스트라는 미확정 노드 중 시간이 가장 작은 노드를 모두 훑어 찾으므로, 전체 비용은 O(n²) 입니다. E가 n²에 가까운 조밀 그래프에서는 이 방식이 더 효율적입니다. 3,000개의 노드와 4,000개의 링크로 이루어진 그래프처럼 희소 그래프에서는 힙 버전이 훨씬 적은 작업을 수행합니다.

보통최단 경로 그래프 힙

+10

네트워크에는 1부터 n까지 레이블이 지정된 n개의 노드가 있습니다. 링크 times[i] = [u, v, w]는 신호를 노드 u에서 노드 v로 w 시간 단위 동안 전달하며, 이 방향으로만 전달합니다.

시간 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
설명: 직접 연결 경로는 시간 4에 노드 2에 도달하지만, 노드 3을 거치는 경로는 1 + 2 = 3에 도착합니다. 노드 4는 신호를 가장 늦게, 3 + 1 = 4에 받습니다.

후속 질문

신호가 m개의 링크를 지난 후 약해진다고 가정해 보세요. 이 제한에서 마지막 노드가 신호를 듣는 시간을 어떻게 찾을 수 있을까요?

힌트

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

3개 중 0개 열림

풀이

각 노드는 k에서 가장 빠른 경로의 길이만큼 시간이 지난 뒤 신호를 받으므로, 이는 단일 시작점 최단 경로를 구한 다음 최댓값을 찾는 문제이며, 경로가 없는 노드는 -1입니다. 간선의 시간은 음수가 될 수 없으므로 다익스트라 알고리즘은 각 노드를 한 번만 확정합니다. 아래에서 E는 times.length입니다.

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

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

핵심 아이디어

k 깊이에서부터 시간의 현재값을 누적하며 깊이 우선 탐색을 하고, 각 노드에 가장 빠르게 도착한 시간을 기록합니다. 기록된 시간보다 빠르지 않게 노드에 도달하는 경로는 탐색을 중단하고, 더 빠른 경로는 기록을 갱신한 뒤 계속 탐색합니다. 가장 빠른 경로는 어느 시점에 기록을 갱신하므로, 각 기록은 결국 실제 최단 시간에 도달합니다.

노드는 여러 번 기록을 갱신할 수 있습니다. 게이트 18개를 일렬로 놓고, 각 쌍을 비용이 없는 링크와 65,536, 32,768에서 시작해 1까지 절반씩 줄어드는 우회로로 연결해 보세요. 우회로를 먼저 시도하면, 탐색은 마지막 게이트에 서로 다른 시간 131,072개로 도달하고 매번 그 뒤의 모든 경로를 탐색합니다. 즉, n에 대해 작업량이 지수적으로 증가합니다.

알고리즘

모든 최단 시간을 무한대로 설정하고 (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

벨먼-포드: 모든 간선을 최대 n-1회 완화

핵심 아이디어

노드마다 잠정 시간 dist를 유지하고, k의 값은 0으로 둡니다. 링크 u → v를 완화할 때 dist[u] + w가 더 작으면 dist[v]를 그 값으로 낮춥니다. Bellman-Ford는 각 패스에서 모든 링크를 완화합니다.

노드까지 가는 최단 경로가 k → a → b → v라고 해 봅시다. 첫 번째 패스에서 dist[a]가 확정되고, 두 번째 패스에서 dist[b]가, 세 번째 패스에서 dist[v]가 확정됩니다. 최단 경로는 노드를 반복해서 지나지 않으므로 링크는 최대 n-1개이며, n-1번의 패스로 모든 노드의 값이 확정됩니다.

각 패스의 비용은 O(E)입니다. 먼 쪽 끝에서부터 나열된 3,000개 노드의 체인은 4,000개 링크를 2,999번 훑어야 하므로 완화 작업이 약 1,200만 번 이루어집니다.

알고리즘

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

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

핵심 아이디어

아직 확정되지 않은 노드 중 잠정 시간이 가장 작은 노드는 이미 최종 확정된 상태입니다. 그 노드로 가는 다른 경로는 확정된 노드에서 출발해 시간이 그 노드보다 크거나 같은 미확정 노드를 거쳐야 하며, 이후의 링크들은 시간이 음수가 아니므로 시간만 더 늘립니다. 따라서 그 노드를 확정하고, 그 노드의 링크를 한 번 완화한 다음 반복합니다.

최소 힙은 가장 작은 시간을 찾습니다. 노드의 값이 더 작아지면 새 항목을 넣고 기존 항목은 그대로 둡니다. 꺼낸 항목의 시간이 dist보다 크면 오래된 항목이므로 건너뜁니다. 각 링크는 최대 한 개의 항목을 넣으므로 힙에는 최대 E + 1개의 항목이 들어가며, 전체 시간 복잡도는 O(E log E)입니다.

알고리즘

dist[k] = 0으로 설정하고, 나머지 모든 dist는 무한대로 설정한 다음, 최소 힙에 (0, k)를 넣습니다.
가장 작은 (t, node)를 꺼냅니다. t > dist[node]이면 오래된 항목이므로 건너뜁니다.
w만큼의 시간이 걸리는 각 연결 node → next에 대해, 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이 아니라 시간 4를 반환합니다.
-1을 잊기. 확인 없이 최댓값을 구하면 무한대가 반환되거나 신호를 받지 못한 노드가 감춰집니다.
가장 큰 int 값을 무한대로 사용하기. 그러면 도달하지 못한 u에 대해 dist[u] + w가 음수로 오버플로됩니다. 도달하지 못한 노드는 건너뛰거나 10^9를 사용하세요.

자주 묻는 질문3

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

다익스트라 알고리즘과 이진 힙을 사용하면 O(E log E)이며, 여기서 E는 링크의 개수입니다. E는 최대 n²이므로 이는 O(E log n)과 같습니다. 공간 복잡도는 O(n + E)입니다. 벨만-포드 알고리즘은 O(n · E) 시간이 걸립니다.

다익스트라 알고리즘에는 왜 음수가 아닌 가중치가 필요할까요?

Dijkstra는 확정된 노드를 다시 방문하지 않는데, 이는 이후에 더 짧은 경로가 없을 때만 안전합니다. 이동 시간이 2인 A → B, 이동 시간이 3인 A → C, 이동 시간이 -2인 C → B 링크가 있으면, B를 2로 확정하지만 C를 거치는 경로로는 1에 도달합니다. Bellman-Ford는 음수 이동 시간을 처리합니다.

힙 없이 네트워크 지연 시간 문제를 풀 수 있나요?

네. 일반 배열을 사용하는 다익스트라는 미확정 노드 중 시간이 가장 작은 노드를 모두 훑어 찾으므로, 전체 비용은 O(n²)입니다. E가 n²에 가까운 조밀 그래프에서는 이 방식이 더 효율적입니다. 3,000개의 노드와 4,000개의 링크로 이루어진 그래프처럼 희소 그래프에서는 힙 버전이 훨씬 적은 작업을 수행합니다.

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

함수

제약 조건

예제

힌트

풀이

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

벨먼-포드: 모든 간선을 최대 n-1회 완화

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

함정과 경계 사례

자주 묻는 질문3

비슷한 문제