[백준] 1916번 최소비용 구하기 (Python)

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

1916번: 최소비용 구하기

문제

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째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

 

출력

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

 

import sys
from math import inf

n = int(input())
m = int(input())
mat =[[]for _ in range(n+1)]
visited = [False for _ in range(n+1)]
result_mat = [inf for _ in range(n+1)]
for _ in range(m):
    start_, end_, distance = map(int, sys.stdin.readline().split())
    mat[start_].append([end_, distance])
start, end = map(int, input().split())

def smallest():
    small = inf
    index = 0
    for j in range(len(result_mat)):
        if visited[j]==False and result_mat[j] < small:
            small = result_mat[j]
            index = j
    return index


def dijkstra(x):
    visited[x]=True
    result_mat[x] = 0
    for i in mat[x]:
        if result_mat[i[0]] < i[1]:
            continue
        else:
            result_mat[i[0]] = i[1]
    for i in range(n-1):
        node = smallest()
        visited[node] = True
        for j in mat[node]:
            if result_mat[j[0]] > j[1]+result_mat[node]:
                result_mat[j[0]] = j[1]+result_mat[node]

dijkstra(start)
print(result_mat[end])

전형적인 최단거리 문제이며 다익스트라 알고리즘을 구현해 보는 연습용으로 좋다.

 

문제풀이

먼저 BFS와 유사하게 연결 노드, 방문체크 리스트, 최단거리 리스트를 선언한다.

 

최단거리 리스트는 노드와의 거리를 비교해 노드의 거리가 짧을 시 이를 대입해주어야 하므로 

초기화 시 inf값을 넣어주었다.

 

그다음 dijkstra(x)에 시작노드를 넣으면 

1. 노드와 연결된 노드를 하나씩 꺼내 최단거리에 대입한다.
2. 이후 방문하지 않은 노드 중 거리가 가장 짧은 노드부터 하나씩 꺼낸다.
3. 현재노드에서 다음노드까지의 거리가 최단거리[다음 노드]보다 적을 시 거리를 대입해 준다.

연결된 모든 노드를 방문하면 dijkstra함수가 종료되고

최단거리 리스트에는 시작점부터 각 노드까지 최단거리가 들어가 있으므로 원하는 노드까지의 거리를 알 수 있다.