문제
풀이
그래프 탐색 중 "최단 경로" 문제다. 이 문제는
- 순환인 경우
- 최단거리가 아닌 경로
두 가지를 나눠서 생각하다보니 좀 어려웠다. 사실은 순환인 경우도 최단거리가 아니기 때문에 간단하게 구현이 가능했다.
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})$에 해결이 가능하다.