[백준 11779 파이썬] 최소비용 구하기 2 (골드 3, 다익스트라)

알고리즘 유형 : 다익스트라
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

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

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

graph = [[] for _ in range(n+1)]
for _ in range(m):
    start, end, cost = map(int, input().split())
    graph[start].append((end, cost))
    
start_city, end_city = map(int, input().split())

# 다익스트라 알고리즘
# 반환 값은 3개
# 1. 최소 비용
# 2. 최단경로 역추적을 위한 linked list와 유사한 느낌의 리스트
# 3. 이동한 도시의 개수
def dijkstra(start_city, end_city):
    SSSP = [INF]*(n+1)
    SSSP[start_city] = 0
    path = [0]*(n+1)
    # path[idx]는 idx까지의 최단경로 상에서,
    # idx 방문 바로 이전의 노드를 의미
    path[start_city] = 0
    count = [0]*(n+1)
    q = []
    heapq.heappush(q, (0, start_city))
    
    while q:
        cnt_cost, cnt_city = heapq.heappop(q)
        
        if cnt_cost > SSSP[cnt_city]:
            continue
        
        for adj_city, adj_cost in graph[cnt_city]:
            cal_cost = cnt_cost + adj_cost
            
            if cal_cost < SSSP[adj_city]:
                SSSP[adj_city] = cal_cost
                path[adj_city] = cnt_city
                count[adj_city] = count[cnt_city] + 1
                heapq.heappush(q, (cal_cost, adj_city))

    return (SSSP[end_city], path, count[end_city])

min_cost, linked, count = dijkstra(start_city, end_city)

# 최단경로 역추적
path = [end_city]
prev = end_city
for _ in range(count):
    path.append(linked[prev])
    prev = linked[prev]
    
print(min_cost, len(path), " ".join(map(str, path[::-1])), sep="\n")

풀이 요약

1. 다익스트라에 최단경로 역추적을 섞은 간단한 문제이다.

   최단경로 역추적을 위한 여러가지 방법이 있는데, edge relaxation과 똑같은 방식으로 최단경로를 이전 노드 최단경로 + 현재 노드값으로 계속 문자열 형태로 갱신해주는 방법도 있고(또는 리스트를 원소로 가지는 리스트 할당. 갱신할 때 이전 노드 최단경로 리스트 + [현재 노드]),

   idx에 대해, path[idx]가 idx까지의 최단 경로 상에서 idx 직전의 노드를 의미하는 path 리스트를 할당할 수도 있다(단, 이 경우에 idx부터 역추적할 때 거쳐온 도시의 개수가 필요하므로 따로 count 리스트 할당).

   두 번째 방법으로 풀어보자. 시간복잡도 상으로도 이득이고 로직도 이해하고나면 간단하다.

2. 우선 다익스트라로 출발 도시부터 도착 도시까지의 최소 비용을 구하는 함수를 작성한다.

   이제 완성된 다익스트라 코드에 몇 가지를 추가하자.

   path 리스트를 추가한다. path[idx]는 idx도시까지의 최단 경로 상에서, idx도시 오기 직전의 도시를 의미한다. 이런 로직이면 나중에 idx부터 거꾸로 recursive한 느낌으로 역추적하여 최단 경로를 구할 수 있다.

   최소 비용에 대해 edge relaxation이 일어날 때, 인접 노드의 path값(=현재 노드)을 할당해주자.

3. path를 완성했다고 끝이 아니다. path를 idx부터 출발 노드까지 역추적해야하는데, 노드를 몇 번을 거슬러 올라가야 하는지를 모른다.

   그래서, 거쳐온 도시의 개수를 의미하는 count 리스트를 할당해준다. 마찬가지로 edge relaxation이 일어날 때 count를 이전 노드 값에서 +1 해준다.

4. 다익스트라 함수가 끝나고 리턴받은 최소 비용, 최단 경로, count값으로 최단경로 역추적 및 답들을 출력해주면 끝!

배운 점, 어려웠던 점

• 생각보다 쉬웠다. 다만 문자열 형태로 최단경로를 갱신해나가는 방식으로 풀 때, 문자열을 따닥따닥 붙여서 갱신해놓고, 나중에 한 글자씩 떼어내서 출력하는 식으로 작성했는데, 도시 번호가 두 자리수인 경우, 15가 1과 5로 분리가 되버리기에 오답이 되는데 이걸 모르고 놓쳐서 꽤나 당황했었다.