[프로그래머스/파이썬] 배달

 

나의 풀이

import heapq

def solution(N, road, K):
    graph = [{} for _ in range(N)]
    time = [500001 for _ in range(N)]
    time[0] = 0
    heap = [(0, 0)]
    heapq.heapify(heap)
    visited = set()
    answer = 0

    for a, b, c in road:
        if b - 1 in graph[a - 1]:
            graph[a - 1][b - 1] = min(graph[a - 1][b - 1], c)
            graph[b - 1][a - 1] = min(graph[b - 1][a - 1], c)
        else:
            graph[a - 1][b - 1] = c
            graph[b - 1][a - 1] = c

    while heap:
        t, x = heapq.heappop(heap)
        visited.add(x)
        if t > K:
            continue
        for y, c in graph[x].items():
            if y not in visited and time[y] > time[x] + c:
                    time[y] = time[x] + c
                    heapq.heappush(heap, (time[y], y))

    for t in time:
        if t <= K:
            answer += 1

    return answer

 - 시간 초과로 고생했다.

 - 이미 K를 넘어버린 경우와 최단 거리가 아닌 경우를 제외하니 해결됐다.