백준 11779 [최소비용 구하기 2] 파이썬

https://www.acmicpc.net/problem/11779

 

# 백준 11779 최소비용 구하기 2
# 다익스트라 알고리즘을 이용해 최소 비용과 경로를 찾는 문제

import sys, heapq

input = sys.stdin.readline

# 도시(정점) 개수 N
N = int(input())
# 버스(간선) 개수 M
M = int(input())

# dist[i] : 시작점에서 i번 도시까지의 최소 비용 저장
dist = [float('inf') for _ in range(N + 1)]
# routes[i] : 시작점에서 i번 도시까지 오는 경로 저장
routes = [[] for _ in range(N + 1)]
# costs[i] : i번 도시에서 출발하는 (도착 도시, 비용) 리스트
costs = [[] for _ in range(N + 1)]

# 버스 노선 입력 받기
for _ in range(M):
    A, B, cost = map(int, input().split())
    # A → B 로 가는 비용 cost
    costs[A].append((B, cost))

# 시작 도시, 도착 도시 입력
start, end = map(int, input().split())

# 우선순위 큐 (최소 힙)
q = []
# 시작 도시까지의 최소 비용은 0
dist[start] = 0
# 시작 경로는 자기 자신만 포함
routes[start].append(start)
# (비용, 현재 도시) 형태로 푸시
heapq.heappush(q, (0, start))

# 다익스트라 알고리즘 수행
while q:
    d, curr_city = heapq.heappop(q)  # 현재 비용, 현재 도시 꺼내기

    # 이미 더 짧은 경로가 있다면 스킵
    if dist[curr_city] < d:
        continue

    # 현재 도시에서 이동할 수 있는 인접 도시 탐색
    for next_city, next_cost in costs[curr_city]:
        # 새로운 경로 비용이 더 적다면 업데이트
        if dist[curr_city] + next_cost < dist[next_city]:
            dist[next_city] = dist[curr_city] + next_cost
            # 우선순위 큐에 (새로운 비용, 다음 도시) 삽입
            heapq.heappush(q, (dist[next_city], next_city))
            # 경로 갱신 (깊은 복사 후 다음 도시 추가)
            routes[next_city] = routes[curr_city].copy()
            routes[next_city].append(next_city)

# 결과 출력
# 1) 최소 비용
print(dist[end])
# 2) 경로에 포함된 도시 개수
print(len(routes[end]))
# 3) 실제 경로
print(*routes[end])

다익스트라 알고리즘을 이용하되, 경로를 추적하는 조건을 더한 문제이다.

N의 숫자가 작아 배열을 전체적으로 copy하여도 문제 없겠다고 판단하여 해결하였는데,

N이 더 큰 경우에서는 parent를 이용하면 메모리를 더 효율적으로 관리하여 해결할 수 있다.

# 백준 11779 최소비용 구하기 2
# 다익스트라 + parent 배열을 이용한 경로 복원

import sys, heapq
input = sys.stdin.readline

N = int(input())   # 도시 개수
M = int(input())   # 버스 개수

dist = [float('inf')] * (N + 1)  # 최소 비용 저장
parent = [0] * (N + 1)           # 경로 추적용 parent
graph = [[] for _ in range(N + 1)]

# 그래프 입력
for _ in range(M):
    A, B, cost = map(int, input().split())
    graph[A].append((B, cost))

start, end = map(int, input().split())

# 다익스트라
pq = []
dist[start] = 0
heapq.heappush(pq, (0, start))

while pq:
    d, curr = heapq.heappop(pq)
    if dist[curr] < d:
        continue
    for nxt, cost in graph[curr]:
        if dist[curr] + cost < dist[nxt]:
            dist[nxt] = dist[curr] + cost
            parent[nxt] = curr  # nxt의 부모를 curr로 기록
            heapq.heappush(pq, (dist[nxt], nxt))

# 경로 복원
path = []
node = end
while node != 0:      # parent[시작점] = 0 이므로 여기서 종료
    path.append(node)
    node = parent[node]
path.reverse()

# 출력
print(dist[end])          # 최소 비용
print(len(path))          # 경로 길이
print(*path)              # 경로