문제 설명

전체 코드

import heapq

def dijkstra(start,dp,graph):
    dp[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    
    while heap:
        wei, now = heapq.heappop(heap)
        for w, next_node in graph[now]:
            next_wei = w + wei
            if next_wei < dp[next_node]:
                dp[next_node] = next_wei
                heapq.heappush(heap, (next_wei, next_node))

def solution(N, road, K):
    inf = 100000000

    dp = [inf] * (N+1)
    graph = [[] for _ in range(N+1)]

    for i in range(len(road)):
        graph[road[i][0]].append((road[i][2],road[i][1]))
        graph[road[i][1]].append((road[i][2],road[i][0]))

    dijkstra(1,dp,graph)
    count = 0
    for i in range(1, N+1):
        if dp[i] <= K:
            count += 1

    return count

해결 방법

다익스트라 알고리즘 문제의 기초가 되는 문제이다. 만약 다익스트라를 모른다면 https://velog.io/@bbkyoo/%EB%A9%B4%EC%A0%91%EC%A4%80%EB%B9%84%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%9816%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C1
이 것을 보고 오길 바란다.

다익스트라를 안다는 가정하에 바로 코드로 들어가면 road의 정점은 서로 양방향이므로 graph에 양방향의 정점과 그 때의 경로의 값인 road[인덱스][2] 원소를 넣어준다. 그 다음에 heapq를 import 하여 다익스트라에 1 원소를 넣어 1번 정점을 기준으로 한 최단 경로를 구하는 dijkstra를 실행한다. 처음 넣은 start 매개변수를 값 0과 함께 heap에 push하고 heappop을 하면서 graph[now] 원소중 w와 heappop에서 나온 wei를 next_wei에 넣어 dp[next_node]보다 작다면 dp[next_node]에 next_wei를 넣어주고 push 해준다.

그리고 계산 후에 dp값중에서 K이하인 것들을 count+1 해주고 count를 return 한다.