[프로그래머스 Lv2, python] - 배달

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

프로그래머스

import heapq

def solution(N, road, K):
    an=[]
    graph=[[] for _ in range(N+1)] 
    distance = [1e8] * (N+1) # 최소 거리 저장
    for a,b,c in road: # 양방향 그래프 생성
        graph[a].append((b, c))
        graph[b].append((a, c))
        
    def dijkstra(start):
        q = []
        heapq.heappush(q, (0, start)) # 최소 거리, 노드 번호
        distance[start] = 0 # 1번 노드는 거리가 0임

        while q:
            dist, now = heapq.heappop(q) # 최소 거리, 현재 노드 번호
            if distance[now] < dist: # 현재 노드의 최소 거리가 더 작으면 넘기기
                continue               

            for i in graph[now]:
                if dist+i[1] < distance[i[0]] and dist+i[1]<=K: # 최소 거리보다 작거나 K값 이하이면
                    distance[i[0]] = dist+i[1]  # 새로 최소 거리를 저장
                    heapq.heappush(q, (dist+i[1], i[0])) # q에 추가
            
    dijkstra(1)
    for i in distance:
        if i!=1e8: # 무한이 아닌값들만 추출 
            an.append(i)
    return len(an)

처음에 dfs로 시도했다가 계속 안풀려서 다익스트라 알고리즘을 사용하였다