[Algorithm] 11779. 최소비용 구하기2

11779: 최소비용 구하기2

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

• 문제 티어 : G3
• 풀이 여부 : Solved
• 소요 시간 : 00:26:21

정답 코드

import sys, heapq
input = sys.stdin.readline

n = int(input()) # 도시 개수 : 정점
m = int(input()) # 버스 개수 : 간선

arr = [[] for _ in range(n+1)]
for _ in range(m):
  u, v, w = map(int, input().rstrip().split())
  arr[u].append((v, w)) # 시작 정점 : (도착 정점, 가중치)

start, final = map(int, input().rstrip().split())

def dijkstra(arr, start, n):
  costs = [float('inf')] * (n+1)
  path = [-1] * (n+1) # 경로 저장 배열
  pq = []
  heapq.heappush(pq, (0, start)) # (가중치, 시작노드)
  costs[start] = 0

  while pq:
    cur_cost, cur_node = heapq.heappop(pq)
    if costs[cur_node] < cur_cost: # 이미 더 낮은 비용으로 처리된 경우
      continue
    for next_node, cost in arr[cur_node]:
      next_cost = cur_cost + cost
      if next_cost < costs[next_node]: # 다음 노드가 더 낮은 비용으로 초기화될 수 있는 경우
        costs[next_node] = next_cost
        path[next_node] = cur_node # 경로 추적
        heapq.heappush(pq, (next_cost, next_node))
  
  return costs, path

costs, paths = dijkstra(arr, start, n)
print(costs[final]) # 출발 도시에서 도착 도시까지 가는 데 드는 최소비용

route = []
cur = final
while cur != -1:
  route.append(cur)
  cur = paths[cur]
route.reverse()
print(len(route)) # 최소비용을 갖는 경로에 포함되어있는 도시의 개수
print(' '.join(map(str, route))) # 최소 비용을 갖는 경로를 방문하는 도시

접근 방식

기존 다익스트라 템플릿 코드에서 추가적으로 “최소 비용”과 “최소비용을 갖는 경로”의 조건이 추가되었다.

  while pq:
    cur_cost, cur_node = heapq.heappop(pq)
    if costs[cur_node] < cur_cost: # 이미 더 낮은 비용으로 처리된 경우
      continue
    for next_node, cost in arr[cur_node]:
      next_cost = cur_cost + cost
      if next_cost < costs[next_node]: # 다음 노드가 더 낮은 비용으로 초기화될 수 있는 경우
        costs[next_node] = next_cost
        path[next_node] = cur_node # 경로 추적
        heapq.heappush(pq, (next_cost, next_node))

우선순위큐를 순회하면서 이미 더 낮은 비용으로 해당 정점으로의 방문이 가능한지 체크하는 과정을 통해 최소비용을 계산할 수 있다.

이전 문제와 다른 점이 있다면, “최소 비용을 갖는 경로”를 계산하기 위해 path 배열을 추가해줬다는 점이다.

costs : 최소 비용

path : 최소 비용을 갖는 경로

우선순위큐에서 heappop() 으로 나온 cur_node에서 이동할 수 있는 next_node의 가중치가 최소비용의 조건을 만족한다면, path[next_node] = cur_node 로 갱신하며 경로를 저장했다.

배운점 또는 느낀점

다익스트라 감 잃지 말좌! 까먹지 않게 간간이 풀이해야겠다.