[Dijkstra] 프로그래머스 L2 '배달' (Python)

<문제 링크>

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

코딩테스트 연습 - 배달

---

<문제 풀이>

1. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구해야 하므로 다익스트라 알고리즘을 이용
2. 간선은 양방향이므로 그래프에 노드를 서로 추가
3. K 시간 이하로 배달이 가능해야 하므로 비용이 3 이하인 노드 개수를 찾아야 함

<코드>

import heapq

def dikjstra(start,distance,graph):
    q = []
    heapq.heappush(q, (0,start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now]<dist:
            continue
        for i in graph[now]:
            cost = dist+i[1]
            if cost<distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost,i[0]))

def solution(N, road, K):
    answer = 0
    INF = int(1e9)
    distance = [INF] * (N+1)
    
    graph = [[] for _ in range(N+1)]
    for a,b,c in road:
        graph[a].append((b,c))
        graph[b].append((a,c))
        
    dikjstra(1,distance,graph)
    
    for i in range(1,N+1):
        if distance[i]<=K:
            answer += 1

    return answer