난이도 : 골드 3
유형 : 다익스트라, 역추적
https://www.acmicpc.net/problem/11779

문제 접근

한 노드에서부터 다른 노드까지의 최소비용?
그리고 간선의 비용이 모두 양수?
-> 다익스트라 알고리즘 이용.
-> 이 문제는 다익스트라 + 역추적

풀이 흐름

입력으로 그래프(인접 리스트)를 만든다.
dist 배열을 INF로 초기화, prev 배열은 -1로 초기화한다.

다익스트라 실행:
우선순위 큐를 사용하여 현재까지 비용이 가장 작은 노드부터 탐색
더 짧은 경로를 찾을 때마다 dist와 prev를 갱신
목적지에 대한 dist가 최소 비용
prev 배열을 따라가며 경로를 역추적 후 뒤집어 출력

다익스트라 알고리즘 간단 리마인드

다익스트라 : 가중치가 음수가 없는 그래프에서 한 정점으로부터의 최단 경로를 구하는 알고리즘

기본 로직 :
시작점의 거리를 0으로, 나머지는 무한대로 설정
방문하지 않은 노드 중 dist가 가장 작은 노드를 선택
그 노드를 거쳐 다른 노드로 가는 거리가 더 짧다면 갱신
이를 반복

효율을 위해 우선순위 큐(힙)를 사용하면 O(M log N)

다익스트라 처음 만났을 때의 포스팅

해답 및 풀이

import sys
import heapq
input = sys.stdin.readline

n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)] # 인접 리스트 형태로 그래프 초기화 (1-index)
for _ in range(m):
    a, b, c = map(int, input().split()) # a에서 b로 가는 비용 c
    graph[a].append((b, c))  # a번 도시 리스트에 (도착도시, 비용) 추가

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

INF = int(1e9)
dist = [INF] * (n+1) # 시작점에서 각 도시까지의 최소 비용 저장 배열
prev = [-1] * (n+1)  # 경로 복원용: 현재 도시로 오기 전 도시를 기록

def dijkstra(s):
    dist[s] = 0
    heap = [(0, s)]  # (현재까지 비용, 현재 도시) 형태로 힙 초기화
    while heap:
        cost, now = heapq.heappop(heap) # 현재 비용이 가장 작은 도시 꺼냄
        if dist[now] < cost: # 이미 더 짧은 경로로 처리된 도시면 무시
            continue
        for nxt, nxt_cost in graph[now]: # 현재 도시에서 갈 수 있는 모든 다음 도시 탐색
            new_cost = cost + nxt_cost # 다음 도시까지의 누적 비용 계산
            if new_cost < dist[nxt]: # 기존 최소 비용보다 더 짧으면 갱신
                dist[nxt] = new_cost  # 최소 비용 갱신
                prev[nxt] = now       # 경로 기록
                heapq.heappush(heap, (new_cost, nxt))   # 힙에 넣어 다음 탐색 후보로 등록

dijkstra(start)

# 최소 비용
print(dist[end])

# 경로 복원
path = []
cur = end
while cur != -1:
    path.append(cur)
    cur = prev[cur]
path.reverse()

print(len(path))
print(*path)