[이코테] CH09 최단경로 개선된 다익스트라 알고리즘 기본 코드

한번 개념 공부하고 문제도 풀었었지만

여전히 까먹는다

 

까먹지 않도록 장기기억으로 가져가도록 하자

기본 코드는 정말정말 기본이 되어야 하므로

 

이걸 올리고도 한번 더 해봐야겠다는 생각이 들었다

한줄 한줄 이게 왜 존재해야 하는 코드인지 다시 생각해봐야겠다.

시간복잡도 : O(ElogV)

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9

def djikstra(start):
    q = []
    heapq.heappush(q,(0,start)) # 초기 힙 원소 설정 . 0은 거리, start는 노드 번호
    while q: # 큐가 비어있지 않는 동안 진행
        dist, now = heapq.heappop(q) # 거리와 노드번호를 힙에서 뺀다(이때 우선순위로 거리가 가장 작은 노드가 나오게 된다)
        if distance[now] < dist: # 만약 현재 갱신되어있는 거리가 더 작은 경우 (처리할 필요가 없는 경우)
            continue
        for i in graph[now]: # 현재 노드와 연결된 다른 노드들에 대해서 반복문 실행
            cost = dist + i[1] # 현재 노드의 비용과 다음 노드로 가는데 드는 비용의 합
            if cost < distance[i[0]]: # 만약 다음 노드로 가는 비용이 갱신되어있는 값보다 작다면?
                distance[i[0]] = cost # 현재 노드의 최소 거리를 cost로 갱신시켜주면서 더 작은 값으로 바꿔준다.
                heapq.heappush(q,(cost,i[0])) # 거리, 현재 노드 번호는 i[0]이므로 힙에 원소를 넣어준다.
n,m = map(int,sys.stdin.readline().split())
start = int(input())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a].append((b,c)) # a라는 노드에서 b번 노드로, 비용이 c

djikstra(start)
for i in range(1,n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])