📗 배달

프로그래머스

import heapq

def solution(N, road, K):
    def dijkstra():
        heap = []
        heapq.heappush(heap, (start, 0))
        costs[start] = 0
    
        while heap:
            node, cost = heapq.heappop(heap)
        
            if costs[node] < cost:
                continue
        
            for next_node, weight in graph[node]:
                next_cost = cost + weight
            
                if next_cost < costs[next_node]:
                    costs[next_node] = next_cost
                    path[next_node] = node
                    heapq.heappush(heap, (next_node, next_cost))
                    
    start = 1
    graph = [[] for _ in range(N+1)]
    costs = [float('inf')] * (N+1)
    path = [0] * (N+1)
    
    for r in road:
        u, v, w = r
        graph[u].append((v, w))
        graph[v].append((u, w))
        
    dijkstra()
    
    return sum(1 for cost in costs if cost <= K)

• 전형적인 Dijkstra 알고리즘 문제입니다.
• 구조만 외워두면 음의 간선을 포함하지 않는 가중치 그래프에서의 최단 거리를 쉽게 계산할 수 있습니다!
• 그래프 탐색 시간 효율성을 위해 heapq를 이용한 우선순위 큐를 도입하였습니다.