[코딩테스트 문제유형] 파이썬 다익스트라 힙 (백준 11779)

다익스트라 유형 다익스트라라는 최단 경로 알고리즘. 다익스트라로 풀 수 있는 문제 유형이 있어서 유형 정복을 위해 풀었다.

백준에서 정답률이 높은 문제로 골라서 그나마 노가다를 하지 않았습니다. 오랜만에 코딩테스트 준비를 해봤는데 굉장히 머리 아팠습니다.

다익스트라라는 함수를 이해해두고 이걸 사용해서 같은 유형을 푸는 방법으로 대비하려고 했습니다. 풀이과정 힙을 사용한 방법과 루프를 사용한 방법이 있다.

루프를 사용해서 풀었는데 시간초과가 나왔다. 힙으로 바꾸는데 많은 수정이 필요하지는 않았다. # https://www.acmicpc.net/problem/11779 import sys import heapq input = sys.stdin.readline N = int(input()) # 도시 수 M = int(input()) # 버스(간선) 수 graph = [[] for _ in range(N + 1)] # 입력 받으면서 인접 리스트로 저장. for _ in range(M): a...