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

백준 알고리즘 1916번

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

---

1916번

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

그 다음 줄부터 버스의 개수만큼 버스의 정보가 주어진다. 출발도시 도착도시 버스비용

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

(이때 출발도시에서 도착도시로 갈 수 있는 경우만 입력으로 주어진다.)

 

출력으로는 입력에서 마지막 줄에 주어진 출발 도시에서 도착 도시까지 가는데 최소 비용을 출력한다.

---

문제 해결

특정한 출발 도시에서 출발해 도착 도시로 가는 최단 경로를 구하는 문제이다. 

그래서 다익스트라 알고리즘을 사용하였다.

 

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

최단 거리 테이블인 distance에 도시의 개수+1만큼 무한대 값으로 초기화해둔다.

 

dijkstra() 함수

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

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

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

 

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

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

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

---

코드

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

    distance = [INF] * (v + 1)
    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())

    dijkstra(departure, distance, graph)
    print(distance[arrival])

def dijkstra(departure, distance, graph):
    q = []
    distance[departure] = 0
    heapq.heappush(q, (0, departure))
    while q:
        dist, vertex = heapq.heappop(q)
        if distance[vertex] < dist:
            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]))

main()

---

결과

---