[백준] 1916번 : 최소비용 구하기

문제

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

풀이

[백준] 1916 : 최소비용 구하기 🥇(골드 5)
🎯 32.239%
⏰ 걸린 시간 : 40분 (1446 지름길 풀고 풀어서 그런지 풀리긴 하는데.. 연습 필요)
⏲ 시간복잡도
: 다익스트라 -> O(ElogV) : EV인데 우선순위 큐 사용해주면 탐색이 logV로 줄어든다.

• 알고리즘 유형 : [다익스트라]

✅ 문제 요약

0. 첫째 줄에 도시의 개수 둘째 줄에는 버스의 개수 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다.
1. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다.
2. N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다.
3. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라.

✅ 출력

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

✅ 풀이방법 & 다익스트라 알고리즘로 푼 이유?

✔️ 전형적인 최단 경로 문제이다.
0. 다익스트라 : 한 정점에서 모든 정점까지의 거리를 계산함
1. 가는 길을 택하는데 최소의 거리 길이를 택하여서 가야하기 때문이다.
2. 플로이드 워셜의 경우는 시간 복잡도가 O(V^3)인데 D의 입력이 10,000이기 때문에 2초를 초과 할 수 있다.

코드(code)

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9) #무한을 의미하는 값으로 10억을 설정
# N : 도시의 개수 , M: 버스의 개수
N = int(input())
M = int(input())

#출발 도시번호, 도착지 도시번호, 버스 비용
cost = [INF] * (N+1) #[INF, INF, INF,INF,INF]
graph = [[] for _ in range(N+1)]
for i in range(M):
    s,e, c = map(int,input().split()) # s: start, e: end, c: cost
    graph[s].append((e,c))
start, end = map(int, input().split())
# print(graph)
# [[], [(2, 2), (3, 3), (4, 1), (5, 10)], [(4, 2)], [(4, 1), (5, 1)], [(5, 3)], []]
def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    cost[start] = 0 #시작 시점의 비용은 0이므로
    while q:
        # print("⏰",q)

        pay, now = heapq.heappop(q)

        if cost[now] < pay: # 비교하기 위한 비용이 여태까지의 cost들중 선정된 비용보다 크면 아래 생략 [⏰ 이줄 없으면 시간초과 발생]
            continue

        for e, c in graph[now]:
            now_cost = pay + c
            # print("🌙",now_cost,pay,c)
            if now_cost < cost[e]: # 도착했지점까지의 비용 < 도착지의 비용 (즉, 더 싼 비용 지불한 경우)
                cost[e] = now_cost
                heapq.heappush(q,(now_cost,e))

dijkstra(start)
print(cost[end])

회고

😼 다익스트라 알고리즘 연습 또 연습!!

• 가중치가 있는 최단거리를 찾는 알고리즘으로는 다익스트라가 적합하다.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/BFS_DFS/Dijkstra/1916(%EC%B5%9C%EC%86%8C%EB%B9%84%EC%9A%A9%20%EA%B5%AC%ED%95%98%EA%B8%B0).py