리트코트 - 743

[정답]

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        
        graph = defaultdict(list)

        for time in times:
            #time[0] = start node, time[2] = cost, time[1] = end node
            graph[time[0]].append((time[2],time[1]))

        costs = {}
        pq = []
        #list pq에 cost, start node를 넣음
        heapq.heappush(pq,(0,k))
        
        while pq:
            current_cost, current_node = heapq.heappop(pq)
            if current_node not in costs:
                costs[current_node] = current_cost
                for cost, next_node in graph[current_node]:
                    next_cost = current_cost + cost
                    heapq.heappush(pq,(next_cost, next_node))
                    
        # 1부터 n개의 노드 방문 기록 확인
        for node in range(1, n+1):
            if node not in costs:
                return -1


        return max(costs.values())

 

[해석]

- 가중치가 있는 그래프로 최소값에서 최대값 찾기 문제 (동시에 노드에 접근할 수 있다는 조건 때문)

- 다익스트라 알고리즘 사용(최단 경로부터 돌기 때문이다.)

- 다익스트라 알고리즘은 우선순위 큐를 이용 이때 가장 효율적인 힙 사용 

- 힙 자체는 우선순위 큐를 위해서 만들어진 자료구조로 가장 시간 복잡도가 낮음(배열, 연결 리스트에 비해서)

- for cost, next_node in graph[current_node]:

  - 자체를 다 돌면 가장 우선순위가 높은(cost, node) cost 기준으로 가장 우선순위가 높은(수가 낮은) 수를 먼저 실행시켜준다. 

 

1. 그래프 구현

2. 우선순위 큐에 시작 조건 넣어주기

3. 1부터 n개의 노드 방문 기록 확인하기

4. 최소값에서 최대값 찾기