[Algorithm] 32강 : 최단 경로 알고리즘 기초 문제 풀이
전보 문제 해결 아이디어 핵심 아이디어 : 한 도시에서 다른 도시까지의 최단 거리 문제로 치환할 수 있다. N과 M의 범위가 충분히 크기 때문에 우선 순위 큐를 활용한 다익스트라 알고리즘을 구현 풀이 구현 import heapq import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 def dijkstra(start): q = [] # 시작 노드로 가기 위한 최단 거리는 0으로 설정하여, 큐에 삽입 heapq.heappush(q,(0,start)) distance[start] = 0 while q: # 큐가 비어있지 않다면 #가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기 dist, now = heapq.heappop(q)..
