04/02 코딩테스트 문제풀이 - 743. Network Delay Time (Leetcode) ⭐⭐⭐⭐⭐

문제

• Leetcode 알고리즘 문제
• 743. Network Delay Time (Medium)
• 문제 내용 : [링크]
  
  

내가 작성한 코드

from heapq import heapify, heappop, heappush
from collections import defaultdict
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        pq = []
        costs = {}

        for time in times:
            graph[time[0]].append((time[2], time[1]))
        
        heappush(pq, (0, k))

        while pq:
            cur_w, cur_v = heappop(pq)
            if cur_v not in costs:
                costs[cur_v] = cur_w
                for cost, next_node in graph[cur_v]:
                    next_cost = cur_w + cost
                    heappush(pq, (next_cost, next_node))
        
        for node in range(1, n+1):
            if node not in costs:
                return -1
        return max(costs.values())
          

• 네트워크 그래프의 모든 vertex를 방문하기 위한 최소 시간을 구하는 문제이다.

• 다익스트라 알고리즘 + 힙 우선순위를 통해 구현한다

• graph, pq, costs를 설정한다.

• graph를 튜플을 활용해 구현한다.
  (time[0] = 현재 노드, time[1] = 다음 노드, time[2] = 소요시간(가중치))

• 첫 시작 노드를 heappush를 통해 추가한다.
  (heappush(pq, (0, k)))

• pq에서 cur_w, cur_v를 heappop(pq) 해준다. cur_v가 costs에 없다면 업데이트 해준다.

• cur_v 기준, 다음 노드(next_node)와 다음 노드까지의 가중치(next_cost)를 구해준다. 다음 노드의 가중치는 현재까지의 가중치(cur_w) + 다음 노드까지 가는cost의 합이다.

• 위에서 구한 next_cost와 next_node를 heappush 해준다.

• 이후, cost에 없는 node가 있는 경우, -1을 return해준다. (즉, 모든 노드를 방문할 수 없는 경우)

• 위의 경우가 아니라면, max(costs.values())를 통해 가장 마지막 노드까지 소요되는 시간을 return 해준다.

⭐⭐⭐⭐⭐

1. 다익스트라 알고리즘 + 우선순위 힙 리스트를 통해 매 순간마다 노드까지의 최소값을 생각해야한다.

2. 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최단 경로를 return 하는 유형의 문제는 다익스트라 + 우선순위 힙을 통해 해결핼 수 있다.