프로그래머스 : 배달

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

코딩테스트 연습 - 배달

 

해결 방법 : 다익스트라

• 다익스트라로 최소비용만 구하면 된다.

from collections import defaultdict
import heapq # 우선순위큐

def solution(N, road, K):
    graph = defaultdict(list)
    
    for f, t, c in road: # 그래프 초기화
        graph[f].append((t, c))
        graph[t].append((f, c))
    
    fees = [float('inf')] * (N + 1) # 1번 마을 기준 최소비용
    fees[1] = 0
    Q = [(fees[1], 1)] # 현재 cost, 현재 마을
    
    while Q: # 다익스트라
        cur_f, cur_n = heapq.heappop(Q)
        if fees[cur_n] < cur_f: continue
            
        for next_n, fee in graph[cur_n]:
            if cur_f + fee < fees[next_n]:
                fees[next_n] = cur_f + fee
                heapq.heappush(Q, (cur_f + fee, next_n))
        
    return len([0 for f in fees if f <= K])