[탐색/다익스트라] 백준 11779 최소비용 구하기 2 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11779번: 최소비용 구하기 2

 

 

 

2. 문제 풀이

 최소의 버스비용으로 A에서 B로 이동하는 문제입니다. 최소비용과 경로를 출력해야 합니다.

2022.05.17 - [Algorithm] - [탐색/다익스트라] 백준 1916 최소비용 구하기 - 파이썬(Python)

 이전 문제인 '최소비용 구하기'에서, '경로 출력'이 추가되었습니다. 다익스트라 알고리즘으로 최적 거리를 찾은 뒤, 역추적해서 경로를 출력해야 합니다.

 

 

2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

[Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

 다익스트라 알고리즘을 통해 최적 경로를 탐색하고, 경로를 역추적하는 내용과 코드는 위 링크에서 보실 수 있습니다.

 

 

 

3. 코드

import heapq  # 우선순위 큐 구현을 위함
import sys
input = sys.stdin.readline

# 입력
N = int(input())  # node 개수
M = int(input())  # edge 개수
graph = [[] for _ in range(N+1)]
parents = [0] * (N+1)  # 이전 노드 저장
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))  # 도착지, 가중치
start, end = map(int, input().split())  # 출발지 목적지

 방향그래프로 입력받습니다. A에서 B로 가는 버스노선이 있다고, B에서 A로 갈 수 있는 건 아닙니다.

 

# 다익스트라 최적경로 탐색
def dijkstra(graph, start):
    distances = [int(1e9)] * (N+1)  # 처음 초기값은 무한대
    distances[start] = 0  # 시작 노드까지의 거리는 0
    queue = []
    heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작

    while queue:  # queue에 남아있는 노드가 없을 때까지 탐색
        dist, node = heapq.heappop(queue)  # 탐색할 노드, 거리

        # 기존 최단거리보다 멀다면 무시
        if distances[node] < dist:
            continue

        # 노드와 연결된 인접노드 탐색
        for next_node, next_dist in graph[node]:
            distance = dist + next_dist  # 인접노드까지의 거리
            if distance < distances[next_node]:  # 기존 거리 보다 짧으면 갱신
                distances[next_node] = distance
                parents[next_node] = node  # 이전 노드 저장
                heapq.heappush(queue, [distance, next_node])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입
    return distances

 다익스트라 알고리즘을 구현합니다. 경로를 역추적할 수 있도록, parents 리스트로 이전 노드를 저장합니다.

 

 

# 출력
dist_start = dijkstra(graph, start)
print(dist_start[end])  # 최소 비용

path = []  # 경로
curr = end
while curr:
    path.append(curr)
    curr = parents[curr]
print(len(path))
for i in path[::-1]:  # 경로 출력
    print(i, end=" ")

 A지점에서 B지점으로 가는 최적 경로를 탐색하고, 비용을 출력합니다. 경로도 역추적해서 출력합니다.