Leetcode - 743. Network Delay Time

문제

풀이

그래프 탐색 중 "최단 경로" 문제다. 이 문제는

• 순환인 경우
• 최단거리가 아닌 경로

두 가지를 나눠서 생각하다보니 좀 어려웠다. 사실은 순환인 경우도 최단거리가 아니기 때문에 간단하게 구현이 가능했다.

DFS

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, t in times:
            graph[u].append((t,v))
            
        total = [float('inf') for _ in range(n)]
        
        def dfs(cur, acc_time):
            # This captures recursive nodes and non-minimum time paths
            if acc_time >= total[cur-1]:
                return
            
            total[cur-1] = acc_time
            
            for t, next in sorted(graph[cur]):
                dfs(next, t + acc_time)
                
        dfs(k, 0)
        if max(total) < float('inf'):
            return max(total)
        else:
            return -1

DFS로 각 노드를 모두 순회해야 하기 때문에 시간 복잡도는 $O(N^N)$에, 각 간선을 정렬하는 복잡도 $O(E\log(E)$를 더한
$$
O(N^N+E\log(N))
$$
이다.

Daijkstra

최단경로 DFS는 다익스트라 알고리즘으로 풀 수 있다.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, t in times:
            graph[u].append((t, v))

        queue = [(0, k)]
        total = {}

        while queue:
            acc_time, node = heapq.heappop(queue)
            if node in total:
                continue

            total[node] = acc_time
            for time, nxt in graph[node]:
                if nxt not in total:
                    heapq.heappush(queue, (time + acc_time, nxt))

        return max(total.values()) if len(total) == n else -1

우선순위 큐를 사용하면 시간복잡도 $O(N\log{N})$에 해결이 가능하다.