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

골드 Ⅲ

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

11779번: 최소비용 구하기 2

 

📄 문제

• n(1≤n≤1,000)개의 도시가 있다.
• 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다.
• 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.
• 항상 시작점에서 도착점으로의 경로가 존재한다.

 

A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라.

---

💡 아이디어

• 일반적인 문제와 다르게 경로도 함께 출력해야한다.
• 경로를 따로 저장해야한다. (route)
• 출발점에서 부터 각 지점까지의 최소 비용를 구한다. (다익스트라 알고리즘)
• 최소 비용를 구하면서 각 지점까지의 경로도 함께 갱신한다. (리스트)
• 저장된 각 도시까지의 최소 비용 중 도착점의 최소 비용을 출력한다. 
• 저장된 경로의 개수를 세어 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다.
• 도착점까지의 최소 비용 경로를 방문한 도시 순서대로 출력한다.

 

반응형

 

📝 문제 풀이 (Code)

import sys, heapq
input = sys.stdin.readline

def dijkstra(start, end):
    global route
    # 비용 저장
    visited = [10000000001] * (n + 1)
    # 비용, 현재 위치
    heap = [(0, start)]
    # 최소 비용 저장
    visited[start] = 0
    # 처음 경로 저장
    route[start] = [start]

    while heap:
        currCost, city = heapq.heappop(heap)

        # 저장된 비용보다 크면 탐색 안함
        if visited[city] < currCost:
            continue

        for nextCity, moveCost in graph[city]:
            totalCost = currCost + moveCost
            # 비용이 적으면 갱신
            if totalCost < visited[nextCity]:
                # 최소 비용 저장
                visited[nextCity] = totalCost
                # 경로 갱신
                route[nextCity] = route[city] + [nextCity]
                # 갱신된 도시 탐색 추가
                heapq.heappush(heap, (totalCost, nextCity))

    return visited[end]


n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    s, e, c = map(int, input().split())
    graph[s].append((e, c))

start, end = map(int, input().split())
# 도시 이동 경로 저장
route = [[] for _ in range(n+1)]
# 출력
print(dijkstra(start, end))
print(len(route[end]))
print(*route[end])