[백준] 11779 - 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

문제 한줄 이해

- 노드들의 최단 경로와 거리를 출력하기

생각난 풀이

1번째 방법: 문제를 읽고 생각난 필요한 조건들

1. 저번에 풀어본 https://9-bin.tistory.com/37   에서 경로까지 출력해야하는 경우다.

->다익스트라, 경로저장 

-> 경로를 어떻게 저장을 해야할지 고민을 해봤지만 쉽사리 떠오르지 않았다. 이때 검색을 해보니 역추적이라는 키워드를 보고 많은 힌트를얻고 풀어보았다.

 

역추적이란 단어에서 얻었던 힌트

->우리는 시작 노드에서 다른 노드로 향할 때 거리 값이 작다면 갱신을 해준다.

그렇다면 방문처리 배열을 만들어 노드를 동시에 저장해준다면 a to b인 상황에서 b로 오는 직전 노드들 중 가장 작은 노드를 저장할 수 있다.

이번 예제를 예를 들면 방문배열에 [[], [], [1], [1], [1], [4]] 이렇게 담겨있다. 

우리는 도착노드가 5번이니깐 5번 직전의 노드들 중 가장 짧은것이 4

그 다음 4번 직전의 노드들 중 가장 짧은것이 1

따라서 경로는 1 4 5가 되는것이다!!!!!!!

 

import sys
import heapq
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[] for i in range(n+1)]
visited = [[] for i in range(n+1)]
for i in range(m):
    a,b,v = map(int,sys.stdin.readline().split())
    graph[a].append((b,v))

start,end = map(int,sys.stdin.readline().split())

def dik(s,e):
    hq = []
    dis = [1e9] *(n+1)
    heapq.heappush(hq,(0,s))
    dis[start] = 0
    while hq:
        tov, nextv = heapq.heappop(hq)
        
        if dis[nextv] < tov:
            continue
        
        for i in graph[nextv]:
            newv = tov + i[1]
            # 거리값이 저장 된 값보다 작다면 거리만 갱신했지만
            # 경로를 담기위해 직전 노드를 저장
            if newv < dis[i[0]]:
                visited[i[0]] = [nextv]
                dis[i[0]] = newv
                heapq.heappush(hq,(newv,i[0]))
    # print(visited)
    
    
    # 역추적을 하기위한 작업
    result = []
    nowv = end
    while nowv != start:
        result.append(nowv)
        nowv = visited[nowv][0]
    result.append(start)
    
    print(dis[end])
    print(len(result))
    print(*reversed(result))
    return
dik(start,end)