백준 1916: 최소비용 구하기

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

알고리즘 분석

• 만약 비용(가중치) 키워드가 없었다면 BFS/DFS로 해결 가능
• 버스 비용와 A에서 B까지 최소비용이라는 키워드 -> 다익스트라

입출력 분석

• A번째 도시에서 B번째 도시까지 가는 최소비용 출력
• 다익스트라 알고리즘을 사용한다면 O(N^2), O(MlongN) 가능
• 시간 제한 0.5초를 고려했을 때, N이 1000이므로 1,000,000 < 50,000,000(0.5초 허용량)
• 따라서 O(N^2)도 통과 가능

---

다익스트라 구현 방식

• 선형 탐색(Greedy) : O(N^2)
• 우선순위 큐 : O(MlogN)

N(Vertext, Node): 정점 = 도시, M(Edge) : 간선 = 버스 노선

해당 문제에서는 두 가지 방식 모두 해결 가능하지만, 우선순위 큐로 해결하는 것이 좋다.

---

풀이

import sys, heapq

input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

start, end = map(int, input().split())


def dijkstra(start):
    q = []

    distances = [INF] * (n + 1)

    heapq.heappush(q, (0, start))
    distances[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distances[now] < dist:
            continue

        for next_node, next_cost in graph[now]:
            cost = dist + next_cost
            if distances[next_node] > cost:
                distances[next_node] = cost
                heapq.heappush(q, (cost, next_node))

    return distances[end]


print(dijkstra(start))

---

결과

구현 포인트 : 그래프 입력, 우선순위 큐, 다익스트라 로직