[백준] 1753. 최단경로_최단경로 - Python

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

 

-----------------------------------------------------------------------------------------------------------------------------------

★ 시작하기 전에

처음 풀어보는 문제 유형, 최단거리 길찾기 문제기존 bfs와 같이 같은 단계에서 확인 후, 넘어가는 것이 아니라 가중치 개념이 포함되어

돌아서 가는 경우 

가 바로 가는 경우 보다 더 빠른 경우가 발생하게 된다.새로운 알고리즘 형식에 대해 익숙해질 필요가 있다.  (다익스트라 알고리즘)

 

다익스트라 알고리즘

- 시작점과 도착할 지점의 정보가 주어진다.

- 연결된 노드 및 가중치 정보가 주어진다.

- 시작점과 모든 지점과의 거리 정보 리스트를 만든다.

- 현재 노드(시작점 포함)와 인접한 모든 노드와의 거리 중 최소 거리인 노드이면서 방문하지 않은 노드 순서대로 방문한다.

- 현재 노드까지의 최소거리 + 두 지점간 최소 거리 < 다음 지점까지 가는 거리 면 갱신해준다.

- 도착지점에 도착하면 알고리즘을 종료한다.

 

python의 경우, 4번째 부분에서 현재노드와 인접한 모든 노드와의 거리 중 최소 거리를 찾기 위해 heapq를 이용하면 빠르게 풀 수 있게 된다.

 

위 문제는 모든 노드를 가는 최소경우를 구하기 때문에 모든 경우를 다 진행하였다.

(추가로 한방향 그래프이기 때문에, visited를 사용하지 않았다.)

import sys
import heapq

input = sys.stdin.readline

INF = 10000000
n, m = map(int, input().split())
start = int(input())

# 노드간 정보를 인접 data로 저장했다.
board = [[] for _ in range(n+1)]
for _ in range(m):
    v, e, k = map(int, input().split())
    board[v].append((e, k)) # 다음점, 거리 표시

# 한방향이라 visited를 활용하지 않아도 된다.

# 시작노드로부터 최소거리를 담고 갱신할 리스트를 만들어 둔다.
ans = [INF for _ in range(n+1)]
ans[start] = 0
q = []
heapq.heappush(q, (0, start)) # 거리와 지점

while q:
	# short는 현재 노드까지의 최소거리, now는 현재 노드 정보이다.
    short, now = heapq.heappop(q)
    # 연결된 노드를 꺼내, 노드정보와 현재노드와의 거리를 가져온다.
    for nextP, l in board[now]:
    	# 현재까지의 최소거리 + 두 노드 사이의 거리와 ans의 시작~노드 거리 비교
        if short + l < ans[nextP]:
            ans[nextP] = short + l
            # 갱신 후에, 가장 최소 거리의 노드부터 q에 넣어 다시 꺼내준다.
            heapq.heappush(q, (short + l, nextP))
for mm in range(1,n+1):
    if ans[mm] == INF:
        print('INF')
    else:
        print(ans[mm])