[맛있는물회] [파이썬] <백준 알고리즘> 1916 번 "최소비용 구하기"

문제 조건

---

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

 

Input

---

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

 

Output

---

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

 

생각한 아이디어

---

다익스트라 문제이다.

 

솔직히 다익스트라 수업때 배우긴했지만 잘 생각이 안나서 복습좀 하고 풀었다.

어제는 1753번

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

1753번: 최단경로

을 풀어봤는데 다익스트라의 방법은 생각은 났지만 왜 min heap을 사용하고, visited가 없어도 되는지가 잘 이해가 안되었는데 오늘 풀면서 싹 이해가 갔다!!

 

*Min Heap

다익스트라의 원리가 current의 vertex에서 가장 가까운 vertex를 먼저 확인한다. 이를위해서 단순한 queue가 아니라 min heap을 사용하게 된다. heap에는 자신이 갈 수 있는 vertex와 거리 즉, weight를 넣어준다.

heap은 여기서 weight를 기준으로 min heap을 구성한다. 

(사실 파이썬의 heapq가 어떤 값을 기준으로 min heap 을 구성하는 지는 모르겠지만 (weight,pos)이렇게 대입하면 첫번째 값인 weight를 기준으로 구성을 하더라)

그렇게 해서 먼저 뽑아낼 값은 가장 가까운 값이 된다.

 

*Visited가 없어도 되는 이유

-> 단방향이기 때문에 다시 돌아갈 일이 없다. 만약 visited로 막아버리면 

예를들어

1->4는 한번 탐색했지만 1->2->4 가 더 짧은 경우일 수도 있기때문에 모든 경우를 탐색해봐야한다. 따라서 visited로 막으면 안된다.

 

 

이 문제에서 좀 신경써야하는 부분은 같은 구간의 버스가 여러대 있을 수 있다는 것이다. 문제에도 그런 조건은 적혀있지 않아서 조금 오바인듯 하다. 

어쨌든 이런 부분을 해결해주고 다익스트라의 기본적인 작동원리를 이해한다면 풀 수 있는 문제이다.

소스코드

import sys
from heapq import heappop,heappush 
input=sys.stdin.readline
INF=sys.maxsize

def dijk(MAP,start):
   dist=[INF for _ in range(n+1)]
   dist[start]=0
   heap=[]
   heappush(heap,(0,start))

   while heap:
      weight,cur=heappop(heap)
      for v in range(1,n+1):
         if MAP[cur][v]!=-1:
            if dist[v] > MAP[cur][v] + weight:
               dist[v] = MAP[cur][v] + weight
               heappush(heap,(dist[v],v))
   return dist


if __name__ == "__main__":
   n,m=int(input()),int(input())
   MAP=[[-1 for _ in range(n+1)] for _ in range(n+1)]
   for _ in range(m):
      u,v,w=map(int,input().split())
      if MAP[u][v] != -1: #같은버스 여러대?
         MAP[u][v]=min(MAP[u][v],w)
      else: MAP[u][v]=w
   start,end=map(int,input().split())
   answer = dijk(MAP,start)
   print(answer[end])

 

*파이썬 문법 정리