배달 힙 다익스트라

import heapq as hq


def solution(N, road, K):
    graph = [[] for _ in range(N + 1)]
    for a, b, c in road:
        graph[a].append((b, c))
        graph[b].append((a, c))

    distance = [float("inf") for _ in range(N + 1)]
    distance[1] = 0
    heap = [(0, 1)]  # 시간, 위치
    while heap:
        time, now = hq.heappop(heap)
        if time > distance[now]:
            continue
        for next, cost in graph[now]:
            new_time = time + cost
            # 더 적은 시간 갱신
            if new_time < distance[next]:
                distance[next] = new_time
                hq.heappush(heap, (new_time, next))

    return sum(d <= K for d in distance)


print(solution(N, road, K))
"""
1번 마을로 부터 가까운 마을부터 확장시키며
더 짧게 갈 수 있는지 계속 업데이트
모두 돌면
1번 마을로부터의 최소 거리들이 나옴
""" ""

 

다익스트라(Dijkstra) 알고리즘이란?

한 지점(출발점)에서 모든 다른 지점까지의 최소 이동 거리(또는 최소 시간)를 구하는 알고리즘이야.

 

• 힙 다익스트라: 매번 현재까지 시간이 가장 작은 정점을 꺼내서 확정 → 최단거리 불변성 유지
• 일반 큐 BFS: 들어온 순서대로 꺼냄 → 더 오래 걸리는 경로가 먼저 처리될 수 있음 → 오답이 되거나, 여러 번 재방문해야 해서 비효율 폭증

BFS는 거리나 시간이 1로 동일해야지 쓸 수 있음

 

 

 

• 다익스트라(Dijkstra) 는 "가중치가 양수인 그래프"의 최단거리를 구하는 알고리즘이고,
• BFS 는 "모든 간선의 가중치가 동일(1)"인 그래프의 최단거리를 구하는 특수한 경우야.

즉,

가중치가 전부 1인 그래프에서는 다익스트라가 BFS와 완전히 동일한 결과를 낸다.
단지 구현이 더 복잡하고, 성능이 살짝 느릴 뿐이야.

가중치 1인 그래프에서 시작점에서 제일 몇 노드들 개수 구하기 같은건 BFS