[프로그래머스(파이썬/Python)] 배달

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

코딩테스트 연습 - 배달

 

전형적인 다익스트라 알고리즘 문제입니다.

 

먼저, 문제에서 임의의 두 지점 사이 가는 경로가 여러 개 주어질 수 있다고 했으므로 가장 짧은 거리만 배열에 저장하도록 처리를 해줘야 합니다. 이는 기존에 저장된 cost값과 현재 input으로 주어진 cost값을 비교하면 되겠죠?

 

다익스트라를 구현할 때는 우선순위 큐(Priority Queue)를 이용하여 현재 노드에서 다른 노드까지의 최소 비용을 갱신해나가면 됩니다. 다익스트라 알고리즘은 기본적으로 Greedy하게 진행되기 때문에 우선순위 큐를 쓰는 것은 필연적이겠죠?

 

[풀이]

import heapq
inf = int(1e10)
def dijkstra(start, graph, N, K):
    distance = [inf] * (N+1)
    distance[1] = 0

    q = []
    heapq.heappush(q, (0, start))

    while q:
        # 현재 노드를 꺼낸다.
        dist, now = heapq.heappop(q)
        if dist < distance[now]:
            continue
        # 현재 노드에서 다른 노드까지 비용 갱신
        for nodeIndex, cost in enumerate(graph[now]):
            if distance[nodeIndex] > cost + dist:
                distance[nodeIndex] = cost + dist
                q.append((cost + dist, nodeIndex))
    answer = 0
    print(distance)
    for d in distance:
        if d <= K:
            answer += 1
    return answer 

def solution(N, road, K):
    graph = [[inf] * (N+1) for _ in range(N+1)]
    # 그래프의 거리 정보 초기화
    for sour, dest, cost in road:
        if cost < graph[sour][dest]:
            graph[sour][dest] = cost
            graph[dest][sour] = cost

    # 자기 자신까지 가는 거리는 0으로 초기화
    for i in range(1, N+1):
        graph[i][i] = 0
    return dijkstra(1, graph, N, K)