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

---

1. 전체 코드

from collections import defaultdict
import heapq

def solution(N, road, K):
    answer = 0
    graph = defaultdict(list)
    distance = defaultdict(int)
    # [start, dest, cost], 양방향으로 추가
    for start, dest, cost in road:
        graph[start].append((dest, cost))
        graph[dest].append((start, cost))

    # q = [(거리, 노드)]
    q = [(0, 1)]
    while q:
        time, node = heapq.heappop(q)
        if node not in distance:
            distance[node] = time;
            # 목적지 노드 = v
            # 거리 w
            for v, w in graph[node]:
                alt = time + w
                heapq.heappush(q, (alt, v))

    for i in distance:
        if distance[i] <= K:
            answer +=1

    return answer

n = 5
r = [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]
k = 3
print(solution(n, r, k))

---

2. 후기

1. 다익스트라 알고리즘을 사용하여 풀면된다. 양방향 이동이 가능한 그래프이기 때문에 start와 dest둘다 거리를 추가해준다.