[이코테] CH09 최단경로 실전문제 3번 전보

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 = []
    distance[start] = 0
    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
                heapq.heappush(q,(cost,i[0]))
    
N,M,C = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a].append((b,c))
distance = [INF] *(N+1)
        
count = 0
sum = 0
maxValue = 0
djikstra(C)
for i in distance:
    if i!=INF and i!=0:
        count +=1
        maxValue = max(maxValue,i)
        
print(count,maxValue)

사실 저 위에 코드를 암기해두고

눈 감고도 쓸 수 있을 정도로(물론 이해를 기반해서..)

장기 기억으로 가져간 이후에

상황을 이해하면

문제가 굉장히 빨리 풀린다

다익스트라 알고리즘?

-> start 노드를 명시해주고 각 노드까지의 최단거리를 구할 수 있다.

여기서 우선순위를 이용하므로 heapq 라이브러리를 사용하여 문제를 푼다 ! 

이걸 기억해두고 다른 문제들 또한 열심히 풀어봐야겠다.