프로그래머스 [lv2] 배달 파이썬

 노드 간의 최소 거리를 다익스트라 알고리즘으로 구하는 문제이다. 

1번 노드를 기준으로 최소 거리를 구하는데, heap 혹은 deque 을 사용하여 접근 할 수 있다. 

 

🍎  heap 을 사용한 풀이

import heapq


def solution(N, road, K):

    distance = [float('inf')] * (N + 1)
    adj = [[] for _ in range(N + 1)]

    for r in road:
        adj[r[0]].append([r[2], r[1]])
        adj[r[1]].append([r[2], r[0]])

    distance[1] = 0
    heap = []
    heapq.heappush(heap, [0, 1])
    while heap:

        cost, node = heapq.heappop(heap)
        for c, n in adj[node]:
            if distance[n] > cost + c:
                distance[n] = cost + c
                heapq.heappush(heap, [distance[n], n])
    return len([i for i in distance if i <= K])

위 풀이는 최소 heap 을 사용한다.

10 ~ 11 라인에서, r[2] 가 첫번째 원소로 append 되는데, 이는 r[2] 가 distance 를 의미하기 때문이다.

우리는 최소 거리를 구하는 문제를 풀고 있기 때문에, 거리에 해당되는 r[2] 를 최소 heap 의 첫번째 인자에 넣는 것이 옳다.

 

🌊  deque 을 사용한 풀이

from collections import deque


def solution(N, road, K):
    adjacent = dict()
    distance = {i: float('inf') if i != 1 else 0 for i in range(1, N + 1)}
    for n1, n2, d in road:
        adjacent[n1] = adjacent.get(n1, []) + [(n2, d)]
        adjacent[n2] = adjacent.get(n2, []) + [(n1, d)]

    que = deque([1])
    while que:
        cur_node = que.popleft()
        for n2, d in adjacent[cur_node]:
            if distance[n2] > distance[cur_node] + d:
                distance[n2] = distance[cur_node] + d
                que.append(n2)

    return len([i for i in distance.values() if i <= K])

deque 과 dictionary 를 사용한다.

dictionary 의 get() 메소드를 유용하게 사용할 수 있는데, 사용하고자 하는 key가 dictionary에 존재하지 않는 경우엔, get() 의 2번째 인자를 value 값으로 대체한다.

 

🌀  시행착오

deque을 사용한 풀이 마지막 라인에서, distance 딕셔너리를 for 문으로 돌릴 때, distance.values() 가 아닌 distance 자체를 넣었다. 거리값(value) 이 아닌 노드 (key) 값이 들어갔기 때문에 엉뚱한 답이 나왔다.