😤 백준 1753번 최단경로 풀이 (Dijkstra Algorithm)

---

이 게시물은 개인적으로 알고리즘 공부한 내용과 이곳 저곳 검색하여 얻은 정보, 잡지식을 꾸준히 쌓아가는 글입니다. 출처는 최하단에 남겨두겠습니다. 자료나 궁금한점은 댓글로 질문해주세요.^^ 

---

Dijkstra Algorithm 
다익스트라 알고리즘 = 데이크스트라 알고리즘 

백준 1753번 최단 경로 문제에 다익스트라 알고리즘이 등장한다. 

원본 풀이는 해당 블로그로 이동!

 

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오.
단, 모든 간선의 가중치는 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를 출력하면 된다.

 

풀이

import sys, heapq  						#sys는 정보입력을 위해, heapq는 다익스트라르 위해 사용
input = sys.stdin.readline				#input으로 설정해준다.	
INF = sys.maxsize						#INF의 값을 설정해준다.
V, e = map(int, input().split())		#V는 노드의 갯수, e는 노드간의 길의 갯수
k = int(input())  						#k는 시작노드
dp = [INF] * (V + 1)					#비어있는 가중치 테이블을 설정해준다. V번 노드도 생성되야 하므로 V+1로 설정해준다.
heap = []								#heap을 선언해준다. 
graph = [[] for _ in range(V + 1)]		#비어있는 맵이라고 보고 선언해준다.가중치테이블과 마찬가지로V+1개 생성해준다.

# 다익스트라
def Dijstra(start):
    dp[start] = 0 						#start = 1이고, 해당 시작점은 가중치를 0으로 하기로 했다.(조건에 나옴)
    heapq.heappush(heap, (0, start))	#초기 시작점을 heap에 넣어준다. 튜플형식
    while heap:							#heap더이상 없을 때까지 진행
        wei, now = heapq.heappop(heap)	#wei가중치, now노드 (처음에는 0,1이 될것이다.) 
        if dp[now] < wei: 				#
            continue
        for w, next_node in graph[now]:	#w가중치, next_node다음노드 의 값을 Graph에 있는 now현재노드 것을 가져온다.
            next_wei = w + wei			#다음 노드로 가는 가중치를 계산한다. w가중치에 heap에 들어있던 Wei를 더해준다.

            if next_wei < dp[next_node]:#next_wei가 dp가중치 테이블에 저장되어있는 다음노드 next_node에 있는 값보다 작다면 성립
                dp[next_node] = next_wei#해당 next_node가중치테이블에 값을 최신화 해준다.
                heapq.heappush(heap, (next_wei, next_node))#heap에 다음 가중치와 다음 노드의 값을 추가해준다.

for _ in range(e):						#노드간의 길의 갯수 만큼 반복문을 통해 graph를 만든다.
    u, v, w = map(int, input().split())
    graph[u].append((w, v))				#graph에 n노드에 w, v 가중치,다음노드의 값을 넣어준다.

Dijstra(k)								#k시작점을 다익스트라 알고리즘에 넣어서 돌려준다.
for i in range(1, V + 1):				#노드점의 갯수만큼 반복문을 통해서 해당 가중치 테이블을 검사한다. 1부터 시작한다.
    print("INF" if dp[i] == INF else dp[i])#INF값이 있다면 INF를 출력하고 값이 있다면 해당 값을 출력한다.

 

이 문제의 핵심은 다익스트라 알고리즘을 활요하여 최단경로를 구하는 것이다.

 

원리는 출발 노드 u , 도착 노드 v 사이의 길을 다 검사해서 제일 작은 값을 가중치 테이블 dp에 최신화 시키는 것이다. 

 

가중치를 해당 노드까지의 거리라고 생각하는 편이 이해하기 쉽다. 

 

모든 경우의 수를 비교하고 해당 거리가 가장 짧은 값을 dp테이블에 최신화 해준다고 이해하면 된다. 

이러한 원리는 heap을 통해서 진행한다.