백준 11779번 <최소비용 구하기2>

백준 알고리즘 11779번

www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

---

11779번

입력으로 첫 줄에 도시의 개수 N이 주어지고 두 번째 줄에 버스의 개수 M이 주어진다.

그리고 M개의 버스 정보가 주어진다. 출발도시 도착 도시 버스 비용

마지막 줄에는 우리가 구하고자 하는 출발 도시와 도착 도시가 주어진다.

 

출력은

첫 줄에는 입력에서 마지막 줄에 들어온 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 

두 번째 줄에는 최소 비용을 갖는 경로에 포함되어 있는 도시의 개수를 (출발 도시와 도착 도시 포함)

세 번째 줄에는 최소 비용을 갖는 경로를 

출력한다.

---

문제 해결

특정한 출발 도시에서 다른 도시까지의 최소 비용을 구하는 문제이기 때문에 다익스트라 알고리즘을 사용했다.

 

버스의 정보를 graph라는 2차원 리스트에 인접 리스트 방식으로 저장해두었다.

 

dijkstra() 함수

1. 최단 거리를 저장할 distance 리스트(1차원)와 최단 거리 경로를 저장할 path 리스트(2차원)를 초기화한다.

2. distance[출발 도시]를 0으로, path[출발 도시]를 [출발 도시]로 설정하고 힙에 (0, 출발 도시)를 넣는다.

3. 힙에서 가장 작은 값을 꺼낸다. (dist, vertex) -> 출발 도시에서 vertex까지 가는데 dist만큼 거리이다.

   dist가 distance[vertex]보다 크면 이미 vertex를 가는데 최소 거리를 구한 것이므로 갱신할 필요가 없다. continue

   

   graph[vertex] 만큼 for문을 돌린다. i = (도시a, 비용) -> vertex에서 도시a까지의 거리가 비용이다.

   dist와 i[1]을 더한 값이 distance[i[0]]보다 작으면 최소 거리가 갱신된 것이므로 distance와 path를 갱신하고 

   힙에다가 (dist+i[1], i[0]) 를 넣는다. -> 출발 도시에서 i[0]까지 가는데 dist+i[1]만큼 거리이다.

 

#path를 갱신하는 것은 힙에서 꺼낸 vertex까지의 path에 i[1]을 추가한 리스트로 갱신하였다. 그러면

 출발 도시에서 vertex까지의 path와 그리고 vertex에서 i[1]까지니까 출발 도시에서 i[1]까지의 최단 거리 path가 된다.

---

코드

import heapq
INF = int(1e9)
def main():
    v = int(input())
    e = int(input())

    graph = [[] for i in range(v+1)]
    for i in range(e):
        start, end, value = map(int, input().split())
        graph[start].append((end, value))
    departure, arrival = map(int, input().split())

    distance, path = dijkstra(departure, graph, v)

    print(distance[arrival])
    print(len(path[arrival]))
    for i in path[arrival]:
        print(i, end=" ")


def dijkstra(begin, graph, v):
    distance = [INF] * (v + 1)
    path = [[] for i in range(v + 1)]
    q = []
    distance[begin] = 0
    path[begin] = [begin]
    heapq.heappush(q, (0, begin))

    while q:
        dist, vertex = heapq.heappop(q)
        if dist > distance[vertex]:
            continue
        for i in graph[vertex]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                temp = path[vertex] + [i[0]]
                path[i[0]] = temp
    return distance, path

main()

---

결과

---

이 문제에서 어려운 부분은 경로를 구하는 부분이라고 생각한다.

최소 비용을 구하는 것은 그냥 숫자를 하나 갱신하면 되는 부분인데 경로를 구하는 것은 어떻게 해야할지 처음엔 생각이 잘 나지 않았다.