[Level 2] / [Python] 배달 - 다익스트라 (Dijkstra)

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

프로그래머스

---

다익스트라 알고리즘을 적용하여 해결

 

import heapq

def dijkstra(dis, visited):
    heap = []
    heapq.heappush(heap, [0, 1])
    
    while heap:
        cost, node = heapq.heappop(heap)
        for c, n in visited[node]:
            if cost + c < dis[n]:
                dis[n] = cost + c
                heapq.heappush(heap, [cost + c, n])


def solution(N, road, K):    
    dis = [float('inf')] * (N+1)
    visited = [[] for _ in range(N+1)]
    
    dis[1] = 0 # 마을 1
    
    for r in road:
        # 거리, 목적지
        visited[r[0]].append([r[2], r[1]])
        visited[r[1]].append([r[2], r[0]])
    
    dijkstra(dis, visited)
    
    return len([x for x in dis if x <= K])