[최단경로 다익스트라] 배달 (프로그래머스, Level2)

문제

배달

• 1번 노드에서 N개의 각 노드로 음식 배달을 진행한다. 음식 배달 시 각 노드에 도달할 수 있는 최단 경로를 구하고, 해당 최단 경로가 K 이하인 노드의 개수를 answer로 리턴해라.
• N : 총 노드의 개수, K : 배달 가능한 최대 경로
• 시작 지점 : 노드 1

그래프

입출력 예시

소스코드

import heapq
INF = int(1e9)
# N: 노드 개수
# K: 배달 가능한 최대 거리
# 시작 지점: 1번 마을

def solution(N, road, K):
    answer = 0      # 자기 자신은 포함
    
    distance = [INF]*(N+1)      # 최단경로 기록
    graph = [[] for _ in range(N+1)]
    for r in road:
        graph[r[0]].append((r[1], r[2]))
        graph[r[1]].append((r[0], r[2]))
    
    queue = []
    start = 1
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    
    
    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now] < dist:
            continue
        else:
            for i in graph[now]:        # i : (node, cost)
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(queue, (cost, i[0]))
    
    for i in distance:
        if i <= K:
            answer += 1

    return answer

실행 결과