[프로그래머스] 배달

접근 방법 : 다익스트라 (BFS + heapq)

heaqp에 넣을 때 인자 순서는 가중치를 앞에 놔 주자.
가지치기(프루닝)를 알게 되었다. 최단 경로 = 다익스트라 잊지 말자.

import sys
import heapq

def solution(N, road, K):
    answer = 0
    max_size = sys.maxsize
    # 다익스트라
    # heapq에 시간, 마을 번호로 집어 넣음
    graph = [[] for _ in range(N + 1)]
    
    for start, dest, time in road:
        graph[start].append((dest, time))
        graph[dest].append((start, time))
    
    deliver_time = [max_size for _ in range(N + 1)]
    deliver_time[1] = 0
    
    que = []
    heapq.heappush(que, (0, 1))
    
    while que:
        time, now = heapq.heappop(que)
        
        # 가지치기 (프루닝)
        if deliver_time[now] < time:
            continue
        
        for next, next_deliver in graph[now]:
            next_time = next_deliver + time
            
            if deliver_time[next] > next_time:
                deliver_time[next] = next_time
                heapq.heappush(que, (next_time, next))
            
    
    for i in range(1, N + 1):
        if deliver_time[i] <= K:
            answer += 1

    return answer