[Python] 프로그래머스 Lv.02 - 배달

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

코딩테스트 연습 - 배달

[ 알고리즘 ]

다익스트라 최단거리 알고리즘

 

[문제 접근]

1에서 출발하여 모든 노드까지의 최단경로를 구하기위해 다익스트라 최단경로 알고리즘을 사용하였음.

힙을 사용하여 매번 최소 경로를 가지고 있는 노드를 반환하는 것이 포인트이다.

 

[코드]

import sys
import heapq


def solution(N, road, K):
    inf = sys.maxsize
    answer = 0

    List = [[] for i in range(N + 1)]
    distance = [inf] * (N + 1)
    distance[1] = 0

    for i in road:
        a = i[0]
        b = i[1]
        w = i[2]

        List[a].append((b, w))  # a에서 b로 가는 최소 거리 w
        List[b].append((a,w))

    heap = []
    heapq.heappush(heap, (0, 1))  # 가중치가 0이고 1을 거쳐서 가는애

    while heap:

        weight, p = heapq.heappop(heap)  # 가중치가 weight이고 p를 거쳐서 가는애

        if distance[p] < weight:
            continue

        for i in List[p]: # p에 연결된 노드의 정보 가져오기
            node = i[0]  # node까지의 거리 갱신
            w = i[1]
            cost = weight + w

            if cost < distance[node]:
                distance[node] = cost
                heapq.heappush(heap, (cost, node))

    result = [i for i in distance if i <= K]
    answer = len(result)

    return answer