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

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

코딩테스트 연습 - 배달

 

다익스트라 알고리즘으로 풀이했다.

주의할 점은 방향성이 없는 간선이므로 도로 정보를 받았을 때 양쪽 마을에 다 추가를 시켜줘야 하고,

간선의 최대 길이는 10,000이지만 배달 시간은 500,000 이하인 것을 주의해서 문제를 풀어야 한다.

 

나의 풀이

import heapq
def solution(N, road, K):
    answer = 0
    INF = 500001
    graph = [[] for i in range(N+1)]
    distance = [INF] * (N+1)
    for r in road:
        a,b,c = r
        graph[a].append((b,c))
        graph[b].append((a,c))
    
    def dijkstra(start):
        distance[start] = 0
        q = []
        heapq.heappush(q,(0,start))
        while q:
            dist, now = heapq.heappop(q)
            if distance[now] < dist:
                continue
            for g in graph[now]:
                cost = dist + g[1]
                if cost < distance[g[0]]:
                    distance[g[0]] = cost
                    heapq.heappush(q,(cost,g[0]))
    dijkstra(1)
    
    for i in range(1,N+1):
        if distance[i] <=K:
            answer +=1
    return answer