최소비용 구하기

알고리즘 구분 : 다익스트라

다익스트라 : 지정된 한 지점에서 지정된 또 다른 지점까지의 최소 비용(or 최단 경로)를 구해야 하는 경우 일반적으로 사용하는 알고리즘으로 지점 간의 비용들이 음의 값을 가지지 않을 경우 사용 가능하다.

다익스트라 알고리즘
1) 출발 노드를 설정
2) 최단 거리 테이블을 무한대의 값을 이용하여 초기화한다. (무한대의 값 : int(1e9))
3) 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다.
4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 계속 갱신한다.

다익스트라 알고리즘 기본

import sys
import heapq

INF = int(1e9)

start = int(sys.stdin.readline().split())

n, m = map(int, sys.stdin.readline().split())

graph = [[] for i in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(m):
    a, b, dist = map(int, input().split())
    graph[a].append((b, dist))

def dijkstra(start):
    q = []
    # 출발노드와 출발노드의 거리 설정 // 단, 출발 노드의 거리는 0
    heapq.heappush(q, (start, 0)) 
    distance[start] = 0
    while q:
    	now, dist = heapq.heappop(q)
        # 이미 처리되어 작아졌다면 다음으로
        if distance[now] < dist:
        	continue
           
        for i in graph[now]:
        	cost = dist + i[1]
            if cost < distance[i[0]]:
            	distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

 dijkstra(start)
 '''
 출처 : 9-2.py 개선된 다익스트라 알고리즘 소스코드 (이것이 코딩 테스트다 with Python, 나동빈)
 '''

문제 풀이 : 문제의 내용 중 다익스트라라고 판단할 수 있도록 근거를 제시해주는 내용은 최소 비용을 출력해야하며, 지정된 한 지점에서 지정된 또 다른 지점까지의 최소 비용을 구해야한다는 것이다. 이는 최단 거리를 구하는 문제 중 다익스트라를 사용하는 유형의 대표적인 특징으로 볼 수 있다. 또한 문제의 내용이 가장 일반적인 다익스트라 알고리즘을 구현하라는 문제이기에 다익스트라 유형임을 파악한다면 쉽게 접근할 수 있었을 것 같다. 실제로 위의 기본 다익스트라 알고리즘 소스 코드와 아래의 문제 풀이 소스 코드가 거의 동일함을 볼 수 있다.

소스 코드 :

import sys
import heapq


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


INF = int(1e9)

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
for _ in range(m):
    a, b, dist = map(int, sys.stdin.readline().split())
    graph[a].append((b, dist))

start, dest = map(int, sys.stdin.readline().split())

dijkstra(start)

print(distance[dest])

• 문제 출처 : https://www.acmicpc.net/problem/1916
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.