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

💁🏻 나의 풀이

import heapq

def solution(N, road, K):
    answer = 0
    graph = {node: {} for node in range(1, N+1)}
    distances = {node: int(2000 * 1e4) for node in range(1, N+1)}
    distances[1] = 0
    queue = []
    heapq.heappush(queue, [distances[1], 1])

    for path in road:
        a, b, c = path
        if b in graph[a] and c >= graph[a][b]:
            continue
        graph[a][b] = c
        graph[b][a] = c

    while queue:
        distance_now, destination_now = heapq.heappop(queue)

        if distances[destination_now] < distance_now:
            continue

        for new_destination, new_distance in graph[destination_now].items():
            distance = distance_now + new_distance
            if distance < distances[new_destination]:
                distances[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])

    for v in distances.values():
        if v <= K:
            answer += 1

    return answer

• 그래프에서 한 노드에서부터 다른 모든 노드까지의 거리의 최소합을 구해야 함 → 다익스트라 알고리즘
• 거리들을 모두 구한 후 거리가 K보다 작은 개수를 구함

👀 다른 사람 풀이

🔗 https://wiselog.tistory.com/73

from queue import PriorityQueue

def dijkstra(road, N):
    dist = [1000000] * (N + 1)
    dist[1] = 0 #시작노드 1은 0
    pq = PriorityQueue()
    pq.put([0,1])

    while not pq.empty():
        cost, here = pq.get()
        if cost > dist[here]: continue

        for i in range(len(road)):
            if road[i][0] == here:
                cost2, there = road[i][2] + cost, road[i][1]
                if cost2 < dist[there]:
                    dist[there] = cost2
                    pq.put([cost2, there])
            elif road[i][1] == here:
                cost2, there = road[i][2] + cost, road[i][0]
                if cost2 < dist[there]:
                    dist[there] = cost2
                    pq.put([cost2, there])
    return dist

def solution(N, road, K):
    answer = 0
    dist = dijkstra(road, N)
    for i in dist:
        if i <= K:
            answer += 1
    return answer

• 마찬가지로 다익스트라 알고리즘을 이용한 풀이
• heapq 대신 PriorityQueue를 사용했다

📚 What I Learned

다익스트라 알고리즘에서 우선순위큐(heapq)로 visited를 대체할 수 있음

• “기존의 다익스트라 알고리즘의 문제점 중 하나는 알고리즘 반복 단계에서 시작 노드와 가장 거리가 짧은 최단 거리 노드를 찾아야 하는데, 이 때 매번 선형탐색을 수행했어야 했다는 것이다.”
• “리스트를 활용하게 되면 삭제 시 최악의 경우 시간 복잡도 O(N)이 걸리는 반면, 힙을 사용하게 되면 최악의 경우라도 삭제 시 시간 복잡도 O(logN)이 걸린다."

PriorityQueue vs heapq

• “PriorityQueue와 heapq는 사실상 동일한데 PriortyQueue는 쓰레드 세이프(Thread-Safe)를 지원하고 heapq는 지원하지 않는다.”