11779. 최소비용 구하기 2 (Python)

11779번: 최소비용 구하기 2

 

풀이

 출발지가 주어졌고 비용에 음수가 없으므로 다익스트라를 이용하여 출발지에서 도착지까지의 최단 거리를 구할 수 있다. 다익스트라는 링크를 참고하자.

 

 문제에서는 단순히 최단 거리뿐만 아니라 경로까지 요구하고 있다. 이를 위해 prev라는 리스트를 추가하였다. prev[x]는 출발지에서 x까지 최단 거리로 이동할 때 x 지점에 도착하기 이전에 방문했던 지점에 대한 정보를 담고 있다. 예를 들어 start -> a -> b -> x와 같은 경로로 이동했다면 prev[x]에는 b라는 지점을 저장하고 있는 것이다. 

 이와 같이 바로 이전에 방문한 지점 정보를 저장한 후 도착지에서 시작하여 출발지를 만나기 전까지 역으로 이전에 방문한 지점을 추적하면 출발지에서 도착지까지 최단 거리로 가는 경로를 구할 수 있다.

 

코드

import sys
import heapq
input = sys.stdin.readline
INF = float('inf')


# 다익스트라
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
    prev[start] = start  # 시작 지점의 이전 도시는 자기 자신으로 설정

    while q:
        nowDist, city = heapq.heappop(q)

        if dist[city] < nowDist:
            continue

        for nextCity, nextDist in buses[city]:
            totalDist = nowDist + nextDist

            # 최단 거리가 갱신되면
            if totalDist < dist[nextCity]:
                dist[nextCity] = totalDist
                heapq.heappush(q, (totalDist, nextCity))
                prev[nextCity] = city  # 다음 도시의 이전 경로를 현재 도시로 설정


if __name__ == '__main__':
    N = int(input())  # 도시의 개수
    M = int(input())  # 버스의 개수
    buses = [[] for _ in range(N+1)]  # 버스 정보
    dist = [INF for _ in range(N+1)]  # 시작 지점에서 다른 지점까지의 최단 거리
    # prev[x] : 시작 지점에서 x 지점까지 최단 거리로 갈 때, x 지점 바로 이전에 들렀던 지점
    prev = [x for x in range(N+1)]

    # 버스 정보 입력
    for _ in range(M):
        a, b, c = map(int, input().split())
        buses[a].append((b, c))

    start, destination = map(int, input().split())  # 출발지, 도착지

    dijkstra(start)  # 다익스트라 수행
    path = [destination]  # 출발지에서 도착지까지의 경로
    nowCity = destination  # 도착지에서 출발지까지 역으로 추적

    while True:
        prevCity = prev[nowCity]  # nowCity로 갈 때 이전에 들렀던 지점
        path.append(prevCity)  # 경로에 추가

        if prevCity == start:  # 시작 지점을 만나면 while문 종료
            break

        nowCity = prevCity

    path.reverse()  # 역으로 추적했으므로 reverse를 통해 뒤집는다.

    print(dist[destination])
    print(len(path))
    print(*path)