[프로그래머스/Level2] 배달

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12978

문제 접근

처음에는 BFS를 이용했다.

노드를 방문하면서 최소 경로를 갱신하는데, 기존과 달리 방문한 노드라도 현재 거리 > 부모의 거리 + 부모와 현 노드의 거리가 만족하면 거리를 갱신하는 방법을 택했는다.

하지만, 절반의 케이스만 성공하여 다익스트라 알고리즘 동작 방법을 공부하여 적용했고 성공했다.

소스 코드

from heapq import heapify
from typing import List


def solution(N: int, road: List[List[int]], K: int):
    distance = [500001] * (N + 1)
    distance[1] = 0
    visit = [False] * (N + 1)

    q = []
    q.append((0, 1))

    while q:
        heapify(q)
        cost, idx = q.pop(0)

        if visit[idx]:
            continue

        visit[idx] = True

        for parent, child, e in road:
            if child == idx:
                parent, child = child, parent
            
            if parent == idx:
                distance[child] = min(distance[child], distance[parent] + e)
                q.append((distance[child], child))

    return len(list(filter(lambda x: x <= K, distance)))