Network Delay Time

강의 출처 : https://www.inflearn.com/course/lecture?courseSlug=%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=146721

학습 페이지

문제 : https://leetcode.com/problems/network-delay-time/

개요

# 접근 방법

 

목적지와 도착지가 있고 가는데 필요한 비용이 주어져있으므로 가중치 그래프를 활용한 문제인 것과 다익스트라 알고리즘을 적용해야 겠다는 생각이 들어야 한다.

 

다익스트라

 

모든 노드를 돌았을 때 최소 값을 출력 -> 최소 비용 중 가장 높은 것 출력(Output) 해야 한다.

 

# 코드 설계

 

- 그래프 구현

 

- 다익스트라 알고리즘

 

- 방문 못한 노드 찾기

 

- 최소값 중 최대값 찾기

 

이 순서로 코드 구현을 한다.

 

코드 구현 전, 실행 시간 초과 되는지 검증해보기

 

# 시간 복잡도 계산

제약 조건

- 그래프 구현

times 의 길이만큼 6000이하 이니 생략 무방

 

-다익스트라 알고리즘  

 

edge 의 갯수만큼 push, pop (O(logn)) 발생 = O(ElognE) E = 는 edge의 갯수

 

결국 6000xlog6000 = 약 13

 

- 방문 못한 노드 찾기

O(n)

 

- 최소값중에서 최대값 구하기

O(n)

 

대략 계산한 결과 시간복잡도상 이상이 없을 것을 확인하였다.

 

 

 

# 코드 구현

import heapq

# input

times = [

  [2,1,2],

  [2,3,5],

  [2,4,1],

  [4,3,3]

]

n = 4

k = 2

# 그래프 구현

def networkDelayTime(times, n, k):

  graph = defaultdict(list) # 딕셔너리 선언, 가중치 그래프 구현

 

  for time in times: # 그래프 채워 나가기

    graph[time[0]].append((time[2], time[1]))

  costs = {}

  pq = []

  heapq.heappush(pq,(0,k))

  while pq:

    cur_cost, cur_node = heapq.heappop(pq)

    if cur_node not in costs: # heap 특성 때문에 처음 방문하는 node가 아니면 최소비용이 아니다.

      costs[cur_node] = cur_cost

      for cost, next_node in graph[cur_node]:

        next_cost = cur_cost + cost

        heapq.heappush(pq, (next_cost, next_node)) # heap으로 인해 가장 높은 우선순위순으로 자동 정렬

가중치 그래프를 구현하는 코드를 작성 후

 

이전에 배웠던 다익스트라 알고리즘 템플릿을 그대로 작성하였다.

 

이 코드를 이제 문제에 맞게 변형 해보자

 

1. 방문 못한 노드가 있는 지 판별하는 for문 추가

for node in range(1, n+1):

    if node not in costs:

      return -1

 

2. return 시 최대값을 찾는 코드 추가

  return max(costs.values())

모든 비용들 중에 가장 큰 값 리턴