Python으로 네트워크 전체에 메시지가 도달하는 데 걸리는 시간 구하기

문제 개요

숫자 n과 간선(edge) 목록이 주어졌다고 가정해 보겠습니다. 0부터 n까지 번호가 매겨진 n+1개의 노드가 하나의 네트워크를 이루고 있습니다. 각 간선은 무방향 그래프에서 (a, b, t) 형태로 표현되며, 이는 a에서 b로 또는 b에서 a로 메시지를 전송할 때 t만큼의 시간이 걸린다는 의미입니다. 어떤 노드가 메시지를 수신하면 즉시 인접한 이웃 노드들에게 메시지를 전파(flooding)합니다. 모든 노드가 서로 연결되어 있을 때, 노드 0에서 시작한 메시지가 모든 노드에 도달하는 데 걸리는 총 시간을 구해야 합니다.

예를 들어 n = 3이고 edges = [[0, 1, 3], [1, 2, 4], [2, 3, 2]]라면 결과는 9가 됩니다. 가장 늦게 도달하는 3번 노드가 0 → 1 → 2 → 3 경로를 통해 메시지를 받기 때문이며, 이때 걸리는 시간은 3 + 4 + 2 = 9입니다.

풀이 접근 방식

이 문제는 다익스트라(Dijkstra) 최단 경로 알고리즘을 활용하면 깔끔하게 해결할 수 있습니다. 시작 노드 0에서 각 노드까지 도달하는 최소 시간을 우선순위 큐(최소 힙)를 이용해 차례대로 확정해 나가고, 모든 노드가 방문 처리되는 순간의 누적 시간이 곧 정답이 됩니다.

알고리즘 단계

1. build_graph() — 그래프 생성

• graph := 빈 딕셔너리(맵)
• edges의 각 (src, dest, t)에 대해 다음을 수행합니다.
  • graph[src]에 (dest, t)를 삽입
  • graph[dest]에 (src, t)를 삽입
• graph를 반환합니다.

2. 메인 로직

• graph := build_graph(edges)
• visited := 새로운 집합
• heap := (0, 0) 쌍으로 초기화한 최소 힙 (누적 시간, 노드)
• heap이 비어 있지 않은 동안 반복합니다.
  • (current_total_time, node) := 힙에서 최솟값 요소를 꺼냄
  • node를 방문 처리
  • 방문한 노드 수가 (n + 1)개와 같다면 current_total_time을 반환
  • graph[node]의 각 (nei, time)에 대해 다음을 수행합니다.
    • nei를 아직 방문하지 않았다면 (current_total_time + time, nei)를 힙에 삽입

Python 구현 예제

아래 구현을 통해 더 자세히 이해해 보겠습니다.

import heapq
from collections import defaultdict
class Solution:
    def solve(self, n, edges):
        graph = self.build_graph(edges)
        visited = set()
        heap = [(0, 0)]
        while heap:
            current_total_time, node = heapq.heappop(heap)
            visited.add(node)
            if len(visited) == (n + 1):
                return current_total_time
            for nei, time in graph[node]:
                if nei not in visited:
                    heapq.heappush(heap, (current_total_time + time, nei))
    def build_graph(self, edges):
        graph = defaultdict(set)
        for src, dest, t in edges:
            graph[src].add((dest, t))
            graph[dest].add((src, t))
        return graph
ob = Solution()
n = 3
edges = [[0, 1, 3],[1, 2, 4],[2, 3, 2]]
print(ob.solve(n, edges))

입력

3, [[0, 1, 3],[1, 2, 4],[2, 3, 2]]

출력

9

동작 원리와 복잡도

최소 힙에서 꺼낸 노드는 항상 현재까지 알려진 가장 짧은 누적 시간을 가지므로, 해당 노드의 최종 도달 시간이 이 시점에 확정됩니다. 따라서 모든 노드(n + 1개)가 방문 처리되는 순간 반환되는 값이 곧 마지막 노드가 메시지를 수신하는 시간, 즉 전체 네트워크 전파가 완료되는 시간이 됩니다.

시간 복잡도는 간선마다 힙 연산이 발생하므로 O(E log E)이며, 공간 복잡도는 그래프 저장과 힙을 위해 O(V + E)입니다. 여기서 V는 노드 수, E는 간선 수를 의미합니다.