프로그래머스: 배달

문제

코딩테스트 연습 - 배달

 

문제 풀이

 문제 조건에 따라 K 시간 이하로 배달 가능한 마을에서만 주문을 받아야 한다. 이때 음식 주문을 받을 수 있는 마을의 개수를 반환하여야 한다. 모든 경우를 `BFS`로 탐색하는 것은 비효율적이다. 따라서 `다익스트라`를 적용하여 탐색을 하게 되면 문제를 해결할 수 있다.

 

코드

from math import inf
from collections import deque


def solution(N, road, K):
    visited = [False] * (N + 1)
    dists = [inf] * (N + 1)
    dists[1] = 0
    q = deque([1])

    while q:
        parent = q.popleft()
        visited[parent] = True

        for node1, node2, dist in road:
            if node1 == parent or node2 == parent:
                target = node1

                if node1 == parent:
                    target = node2

                if dists[target] > dists[parent] + dist:
                    dists[target] = dists[parent] + dist
                    q.append(target)

    return sum(1 for d in dists if d <= K)