[프로그래머스] Lv2 - 배달 (파이썬)

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

코딩테스트 연습 - 배달

 

import heapq
import sys


def solution(N, road, K):
    answer = 0
    arr = [[]for _ in range(N+1)]
    for a, b, time in road:
        arr[a].append((time, b))
        arr[b].append((time, a))
    visited = [sys.maxsize] * (N+1)
    dijkstra(arr, visited)

    return len([x for x in visited if x <= K])


def dijkstra(arr, visited):
    q = []
    heapq.heappush(q, (0, 1))
    visited[1] = 0
    while q:
        cost, node = heapq.heappop(q)
        if visited[node] > cost:
            continue
        for ncost, nnode in arr[node]:
            temp = cost + ncost
            if visited[nnode] > temp:
                visited[nnode] = temp
                heapq.heappush(q, (temp, nnode))

 

최단거리, 다익스트라
1. 인접 리스트로 변환을 하고 visited를 최대 크기로 설정 (visited : 각 노드까지 가는데 걸리는 최소 시간)
2. 다익스트라 (1에서 시작)
    - node에 연결된 다른 노드들과의 최소 비용을 업데이트
    - heap에 push
    - 반복
3. 각 노드까지의 최소 시간이 K이하인 값의 개수를 리턴