BaekJoon 1753번 : 최단경로 (python)

BaekJoon 1753번 : 최단경로(G4 25.525%)

단계별 풀이 중 최단경로 단계에서 첫번째 문제인 최단경로 문제이다.
오늘 다익스트라 알고리즘을 여러문제 풀 것 같아서 어제밤에 미리 알고리즘 영상들을 많이 봐둔게 오늘 문제 푸는데 도움이 많이 된 것 같다.

먼저 다익스트라 알고리즘에 대해서 관찰 알아봐야 할 것 같다.
다익스트라 알고리즘은 BFS로 푸는 최단경로 문제중 조건에 가중치가 붙어있는 문제들을 풀 때 쓰는 알고리즘이다.
큰 원리는 BFS랑 비슷해보이지만 다익스트라 알고리즘에서는 heapq를 쓴다는 것과 가중치를 이용해 비교하는 부분의 차이점이 보인다.

• 기본적으로 문제의 조건에서 주어진 최댓값보다 큰 INF로 두고 기본적으로 각 노드까지의 최단 경로인 distance 값을 INF로 초기화해준다.
• heap자료구조를 통해 다익스트라 알고리즘 내부에서는 가중치와 현재 노드의 위치를 heap에 넣어주고 빼주는 형식으로 동작하게 된다.
• 만약 현재 이미 distance에 들어있는 값이 지금의 heap에서 뺀 가중치보다 작을 경우 이미 최단경로로 이미 처리된 경우이니 continue를 해줌으로써 불필요한 작업을 하지 않게 해준다.
• 만약 위 3번의 조건에 걸리지 않게 된다면 현재 노드와 연결된 노드들을 탐색하며 가중치를 넣었을 때의 갑을 비교해 볼 수 있는 상황이 되게 된다. 만약 현재의 가중치를 더했을 때의 값이 더 작게 된다면 이 값이 지금까지의 최단 경로이기 때문에 값을 현재의 노드에 넣어주고 heap에도 넣어주게 된다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(start) :
    q = list()
    heapq.heappush(q,(0,start))
    while q :
        dis, now = heapq.heappop(q)
        if distance[now] < dis :
            continue
        for i in graph[now] :
            if distance[i[0]] > dis + i[1] :
                distance[i[0]] = dis + i[1]
                heapq.heappush(q,(distance[i[0]],i[0]))
V, E = map(int,input().split())
K = int(input())
graph = [[] for _ in range(V+1)]
check = [False]*(V+1)
distance = [INF]*(V+1)
distance[K] = 0
for _ in range(E) :
    a, b, c = map(int,input().split())
    graph[a].append((b,c))   
dijkstra(K)
for i in range(1,V+1) :
    if distance[i] != INF :
        print(distance[i])
    else :
        print('INF')