[백준] 1753번 최단경로 파이썬 해설 (다익스트라 알고리즘)

출처 : https://www.acmicpc.net/problem/1753

1753번: 최단경로

다익스트라 알고리즘으로 분류된 문제이다.

다익스트라 알고리즘은 하나의 정점에서 나머지 모든 정점까지의 최단 거리를 찾는 알고리즘이다.

모든 정점의 최단거리를 구하는 플로이드-워셜 알고리즘과 다른 알고리즘이니 착각하지 말자!

 

풀이

---

다익스트라 알고리즘의 전체적인 개념은 여기를 참고하면 좋을 것 같다. 누군가 비 전문가인 나의 글을 보고 공부할 것 같아서 차라리 제대로 된 자료를 링크해두는 게 좋을 것 같다고 생각한다.

예제의 입력으로 문제를 풀어보자.

예제의 입력을 적용해서 대충 그려본 그래프이다. (가중치에 비례해서 그려보려고 했지만 실패했다.)

시작점은 1로 주어졌으니 1번 정점에서 다익스트라 알고리즘을 적용시켜보자.

1. 1번에서 직접 갈 수 있는 정점은 2번과 3번이다. 그리고 문제의 조건에서 시작점 자신은 0으로 출력하라고 했으니 고려하여 테이블을 만들어보자.

	1	2	3	4	5
start(1)	0	2	3	INF	INF

*무한대를 INF로 표기

 

2. 현재 테이블 기준으로 자기 자신을 제외한 가장 가까운 정점을 선택하여 테이블을 갱신하는 알고리즘을 수행한다.

현재 과정에서 필요한 부분만 다시 그려봤다.

(1) 현재 테이블에서 가장 가까운 정점을 선택한다. (2번 선택)
(2) 2번 정점에서 갈 수 있는 정점을 조사한다. 

1. 2번에서 3번을 가는 경우를 조사한다.
   2 -> 3의 가중치 4, 2 -> 4의 가중치 5에 관한 데이터를 최소 힙에 넣는다.
2. (2 - 2) 최소 힙에서 가장 가중치가 적은 노드를 선택한다. (2 -> 3의 가중치 4 선택)
   1번에서 2번까지 가는 거리 + 2번에서 3번까지 가는 거리 = 2 + 4 = 6
   현재 테이블에서 3번 노드까지의 거리는 3이고, 1 -> 3으로 가는 경우가 더 최소이므로 다음 단계를 진행한다.
3. 최소 힙에서 가장 가중치가 적은 노드를 선택한다. (2 -> 4의 가중치 5 선택)
   1번에서 2번까지 가는 거리 + 2번에서 4번까지 가는 거리 = 2 + 5 = 6
   현재 테이블에서 4번 노드까지의 거리는 INF로 되어있기 때문에 6 < INF이므로 테이블을 업데이트해준다.
4. 이어어서 탐색할 필요가 있는 노드라고 판단하여 최소 힙에 넣어준다.

(3) (1) ~ (2)의 과정을 최소 힙이 비어질 때까지 반복한다.

 

최소 힙에 대한 설명이 조금 이해가 안 된다면, 최소 힙을 이용한 다익스트라 알고리즘에 대한 개념을 공부하고 오는 것을 추천한다.

 

-정답 코드

import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize
V, E = map(int, input().split())
#시작점 K
K = int(input())
#가중치 테이블 dp
dp = [INF]*(V+1)
heap = []
graph = [[] for _ in range(V + 1)]

def Dijkstra(start):
    #가중치 테이블에서 시작 정점에 해당하는 가중치는 0으로 초기화
    dp[start] = 0
    heapq.heappush(heap,(0, start))

    #힙에 원소가 없을 때 까지 반복.
    while heap:
        wei, now = heapq.heappop(heap)

        #현재 테이블과 비교하여 불필요한(더 가중치가 큰) 튜플이면 무시.
        if dp[now] < wei:
            continue

        for w, next_node in graph[now]:
            #현재 정점 까지의 가중치 wei + 현재 정점에서 다음 정점(next_node)까지의 가중치 W
            # = 다음 노드까지의 가중치(next_wei)
            next_wei = w + wei
            #다음 노드까지의 가중치(next_wei)가 현재 기록된 값 보다 작으면 조건 성립.
            if next_wei < dp[next_node]:
                #계산했던 next_wei를 가중치 테이블에 업데이트.
                dp[next_node] = next_wei
                #다음 점 까지의 가증치와 다음 점에 대한 정보를 튜플로 묶어 최소 힙에 삽입.
                heapq.heappush(heap,(next_wei,next_node))

#초기화
for _ in range(E):
    u, v, w = map(int, input().split())
    #(가중치, 목적지 노드) 형태로 저장
    graph[u].append((w, v))


Dijkstra(K)
for i in range(1,V+1):
    print("INF" if dp[i] == INF else dp[i])

 

 

결과

---

정말 속을 많이 썩인 문제였다.

조금만 잘못 생각해도 틀려버려서 기본 개념에 대해 계속 반복하여 공부했다.

그래도 다시는 안 까먹을 것 같아서 후회는 하지 않는다.