[Python][백준] 1916. 최소비용 구하기/ 다익스트라, 최단 경로 (G5)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

from heapq import heappop,heappush

N = int(input())
M = int(input())
lst = [[] for _ in range(N+1)]

for _ in range(M):
  start,end,cost = map(int,input().split())
  lst[start].append((end,cost))

departure, arrival = map(int,input().split())

distance = [float('INF')] * (N+1)
distance[departure] = 0
queue = [(0,departure)]


while queue :
  current_cost,currnt_node = heappop(queue)

  if current_cost > distance[currnt_node]: 
    continue
  
  for next_node,weight in lst[currnt_node]:
    new_cost = current_cost + weight
    if new_cost < distance[next_node]:
      distance[next_node] = new_cost
      heappush(queue,(new_cost,next_node))


print(distance[arrival])

 

 

1. 다익스트라 알고리즘은 출발점에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 

 

2. 탐욕적으로 접근해야하므로, 우선순위 큐를 사용한다. 

 

3. 먼저 2차원 형태의 lst를 입력 받아준다. 

lst[start].append((end,cost))

 

 

4. 이후 distance 배열을 만들어주는데, 거리의 크기는 갱신하기 때문에 무한대로 설정한다. 

 

5. 그리고 출발점을 queue에 넣고, cost를 0으로 놔준다. 

 

6. 아래 조건은 이미 방문한 경우를 제외하기 위함이다. 

if current_cost > distance[current_node]

7. 그리고 다음 노드의 weight를 현재 cost로 더해 new_cost를 구하고, 다음 노드의  cost와 비교하고 갱신해준다. 

 

8. 갱신에 성공하면 queue에 값을 넣어준다. 

 

📌 문제 코멘트 

" 다익스트라의 개념을 알고 있고, 이것을 코드로 구현 할 수 있는가 ? "

아마 처음 이 문제를 푼다면, 풀기가 매우 어려울 것 같다.

 

이런 유형은 그냥 외워서 이해하는 방향이 좋을 듯 하다. 지난번에도 다익스트라 문제를 푼 것 같은데, 시간이 지나니 ...그래도 얼추 기억은 나니 또 까먹을 때 쯤 한 번 더 풀어 봐야겠다. 

---

📚문제

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

입력

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

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

출력

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

예제 입력 1 복사

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력 1 복사

4