다익스트라 Python (1) 썸네일형 리스트형 [Python] 백준 1753번 문제, 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 다익스트라 알고리즘을 사용해 최단 경로를 구하는 문제이다. 그런데 리스트를 사용한 다익스트라 알고리즘은 모든 정점에 대해 모든 경우를 처음부터 탐색해야 하기 때문에 비효율적이라고 한다. 그래서 우선순위 큐를 이용한다면 최소한으로 모든 경우의 최단 경로를 업데이트 할 수 있다. 이 우선순위 큐는 min_path를 업데이트 했을 때만 push가 되며, 최소힙으로 정렬된다. .. 이전 1 다음