[프로그래머스] Level2, 배달 (Python)

문제

https://programmers.co.kr/learn/courses/30/lessons/12978?language=python3 

코딩테스트 연습 - 배달

 

코드

import sys
import heapq
def solution(N, road, K):
    answer = 0
    INF = sys.maxsize
    graph = [[] for _ in range(N+1)]
    distance = [INF for _ in range(N+1)]
    
    for a,b,c in road:
        graph[a].append((c,b))
        graph[b].append((c,a))
    
    queue = []
    heapq.heappush(queue, (0, 1))
    distance[1] = 0
    def dijkstra():
        while queue:
            wei, now = heapq.heappop(queue)
            if distance[now] < wei:
                continue
            for w, next in graph[now]:
                next_w = w + wei
                if distance[next] > next_w:
                    distance[next] = next_w
                    heapq.heappush(queue, (next_w, next))
    dijkstra()
    for i in range(1, N+1):
        if distance[i] <= K:
            answer += 1
    return answer

 

경로에 가중치가 서로 다르므로 다익스트라를 이용하여 1번정점에서 모든 정점까지 최단경로를 구한다음

 

K보다 작은 정점이 몇개인지 세어주면 된다.