[다익스트라][lv.2] 배달 - 파이썬(Python)

 
 
https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 
 
 
다익스트라 복습겸 풀었다.
 
 
이전에는 deque를 이용한 풀이 방식이었는데...
 
https://jie0025.tistory.com/475

[Summer/Winter Coding(~2018)][lv.2] 배달 - 파이썬(Python), 다익스트라

 
 
이번엔 heapq를 사용한 다익스트라로 구현했다.
 
 

✅ 정답코드

import sys
import heapq

INF = sys.maxsize

def dijkstra(start, distance, graph):
    
    q = []
    
    heapq.heappush(q, (0,start))
    distance[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        
        if distance[now] < dist: #이미 최단거리 갱신된거면 건너뛴다.
            continue
        
        for connect_info in graph[now]: #연결된 친구들 찾기 #now를 거쳐서 가는게 최단거리일 경우 갱신해주기 위함이다.
            new_dist = dist + connect_info[1]  #cost 
            
            if new_dist < distance[connect_info[0]]: #해당노드까지의 거리보다 새롭게 계산한거리가 짧으면
                distance[connect_info[0]] = new_dist
                heapq.heappush(q, (new_dist, connect_info[0]))
        

    
def solution(N, road, K):
    # 1번 노드에서 전체 노드까지의 최단 거리를 찾아야한다 (다익스트라)
    # HeapQ를 써야한다.
    
    
    distance = [INF] * (N+1)
    
    graph = [[] for _ in range(N+1)]
    
    for a, b, cost in road:
        graph[a].append((b,cost))
        graph[b].append((a,cost))
        
    dijkstra(1, distance, graph)
    
    
    answer = 0
    for i in range(1, N+1):
        if distance[i] <= K:
            answer+=1

    return answer