[백준11779] / 최소비용 구하기 2 - 다익스트라

 

백준11779

 

 

푼 날짜 : 2024.11.11

푼 문제 : [11779] / 최소비용 구하기 2

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근 방식 :

사실 다익스트라로 가장 적은 비용을 들이는 것은 어렵지 않았다.

이 문제의 포인트는 적은 비용을 들인 어떤 경로로 왔는가! 이다.

 

따라서 나는 경로에 (어디서 왔는지, 얼마에 왔는지) 를 함께 저장했다.

이렇게 하면 도착점에서 이전 경로로 돌아오면서 경로 파악을 할 수 있다.

 

 

예를 들어 기본 예시로 계산을 해보면 

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

 

dist 는 아래처럼 출력된다.

[(-1, inf), (0, 0), (1, 2), (1, 3), (1, 1), (4, 4)]

 

 

따라서 도착점인 5번 정점에서 출발하면

now = v2(5) 로 초기화

 

[(-1, inf), (0, 0), (1, 2), (1, 3), (1, 1), (4, 4)]

=> 스택에 now(5) 추가, 5번은 4번 정점에서 왔으므로 now = 4

 

[(-1, inf), (0, 0), (1, 2), (1, 3), (1, 1), (4, 4)]

=> 스택에 now(4) 추가, 4번은 1번 정점에서 왔으므로 now = 1

 

now == v1 (1) 이 되었으므로 종료하고

마지막으로 스택에 v1을 추가한다.

 

이렇게 되면 스택의 길이가 방문한 정점의 개수가 되고 이를 전부 pop하면 경로를 출력할 수 있다!

 

 

 

코드 :

import sys
import heapq

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

graph = [[] for _ in range(n+1)]

# (어떤 정점에서 왔는지, 얼마 들여서 왔는지 비용)
dist = [(-1, float('INF')) for _ in range(n+1)]

for _ in range(m):
    s, e, c = map(int, sys.stdin.readline().split())
    graph[s].append((c, e))

v1, v2 = map(int, sys.stdin.readline().split())

heap = [(0, v1)]
dist[v1] = (0, 0)

while heap:
    n_cost, n_node = heapq.heappop(heap)

    if dist[n_node][1] < n_cost: continue

    for cost, node in graph[n_node]:
        all_cost = n_cost + cost

        if all_cost < dist[node][1]:
            dist[node] = (n_node, all_cost) # n_node 인덱스에서 all_cost 비용으로 왔다.
			
            heapq.heappush(heap, (all_cost, node))

st = []
now = v2 # 도착점에서 되돌아가기 위함
while now != v1:
    st.append(now)
    now = dist[now][0]
st.append(v1) # 마지막으로 출발점 추가

print(dist[v2][1]) # 도착점에서의 비용
print(len(st)) # 지나온 정점 개수
while st: print(st.pop(), end=' ') # pop하며 출력하면 순서대로 경로 출력 가능
print()

 

 

다익스트라 재밌다 !!!!

오늘도 한층 성장했다 뿌듯 🥳