문제

BOJ 1916: 최소비용 구하기 https://www.acmicpc.net/problem/1916

풀이

조건

• A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력한다.
• 도시의 개수 N(1 ≤ N ≤ 1,000)
• 버스의 개수 M(1 ≤ M ≤ 100,000)

풀이 순서

• 도시의 개수 N(1 ≤ N ≤ 1,000)를 보면 다익스트라 알고리즘을 사용해야 한다는 것을 알 수 있다.
  • 플로이드-워셜 알고리즘을 사용하면 시간초과가 난다.(O(N^3))

코드

Python

import sys
import heapq

INF = int(1e9)

N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())

# 입력받은 도시와 도시를 잇는 버스 정보 입력
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    s, e, c = map(int, sys.stdin.readline().rstrip().split())
    graph[s].append([e, c])

# 시작 도시, 목표 도시
start, target = map(int, sys.stdin.readline().rstrip().split())

# 처음엔 모든 도시로 가는 거리가 '무한'으로 설정
distance = [INF] * (N + 1)

# 다익스트라 알고리즘을 사용
def dijkstra(start):
    pque = []
    # 시작 도시로 가는 거리와 시작 도시 번호를 넣어줌
    # 파이썬 에서의 HeapQueue(PriorityQueue)는 튜플 0번째 값이 작을 수록 높은 우선순위를 가진다.
    heapq.heappush(pque, (0, start))
    # 시작 도시로 가는 거리는 0으로 설정
    distance[start] = 0

    while pque:
        # 현재 도시로 오는 거리, 현재 도시 번호 순으로 나옴
        dist, now = heapq.heappop(pque)
        # 현재 도시로 오는 최단 거리가 현재 구한 거리보다 작으면 그냥 넘어감
        if distance[now] < dist:
            continue
        # 현재 도시와 연결된 도시들을 차례로 꺼내며 확인
        for node in graph[now]:
            # (현재 도시로 오는 최단 거리 + 연결된 도시까지의 거리)를 cost에 넣음
            cost = dist + node[1]
            # 새로 구한 cost가 연결된 도시로 가는 거리보다 작다면 갱신해줌
            if cost < distance[node[0]]:
                distance[node[0]] = cost
                heapq.heappush(pque, (cost, node[0]))


dijkstra(start)

print(distance[target])

정리

• 다익스트라 알고리즘을 구현하는 부분이 익숙해지도록 더 연습해야겠다.