[프로그래머스] 배달 / 파이썬 / (다익스트라 알고리즘)

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

코딩테스트 연습 - 배달

풀이

전형적인 다익스트라 문제이다.
딱히 풀이과정에 대해 설명할 게 없다.

import heapq as h

def solution(N, road, K):
    answer = 0
    INF = 987654321
    dist = [ INF for _ in range(N+1) ]
    dist[1] = 0
    edges = [ [] for _ in range(N+1) ]
    for (fr, to, w) in road:
        edges[fr].append((to, w))
        edges[to].append((fr, w))
    pq = []
    for (to, w) in edges[1]:
        h.heappush(pq,(w, 1, to)) 
    while pq:
        w, fr, to = h.heappop(pq)
        if  dist[fr] + w < dist[to]:
            dist[to] = dist[fr] + w
            for (tt, ww) in edges[to]:
                h.heappush(pq,(ww,to,tt))
    return len(list(filter(lambda x:x <= K,dist)))