배달

 

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

프로그래머스

문제풀이

최단 경로 알고리즘을 사용해서 풀이해야 하기에 다익스트라 알고리즘을 사용했다.

 

• 트리구조를 그래프화 시켜준다. 이때 (이웃 노드, 거리)를 튜플로 만들어 삽입한다.
• 1번 노드부터 순회하며 해당 노드는 방문처리 해준다. 나머지 노드에 대해선 무한대의 값으로, 힙은 거리 비용을 기준으로 정렬할 수 있게끔 초기화한다.
• 거리 비용이 적은 노드부터 우선 방문하여 이미 최단 거리를 구한 노드라면 건너뛰어준다. 그렇지 않다면 해당 노드의 이웃 노드를 탐색해 주며 현재 노드, 이웃 노드의 거리 비용을 합쳐서 계산한 값이 최단 거리가 아니라면 해당 값을 최단 거리로 경신해 준다.

from collections import defaultdict
import heapq


def solution(N, road, K):
    graph = defaultdict(list)
    for a, b, c in road:
        graph[a].append((b, c))
        graph[b].append((a, c))
    return sum([1 for x in dijkstra(graph, 1).values() if x <= K])


def dijkstra(graph, start):
    dists = defaultdict(lambda: float("inf"))
    dists[start] = 0
    heap = [(0, start)]
    while heap:
        dist, node = heapq.heappop(heap)
        if dist > dists[node]:
            continue

        for n_node, n_dist in graph[node]:
            u_dist = dist + n_dist
            if u_dist < dists[n_node]:
                dists[n_node] = u_dist
                heapq.heappush(heap, (u_dist, n_node))
    return dists