[백준] 1753(파이썬) - 최단경로

[백준] 1753(파이썬) - 최단경로

728x90

https://www.acmicpc.net/problem/1753

이 문제는 제목 그대로 최단경로, 즉 알고리즘 분류 중 다익스트라로 풀어내는 문제이다.

최단경로 문제는 다익스트라와 플로이드 워셜 정도가 있지만 둘이 차이는 아래와 같다.

다익스트라 : 시작점으로 부터 나머지 정점까지 최단거리를 구할 때 플로이드 워셜 : 각 정점간 최단경로를 구할 때

위를 고려해서 문제를 풀어주면 된다. 가장 기본적인 다익스트라 함수를 구현해서 문제를 풀어주었다.

각 인덱스(노드번호)마다 연결되어있는 노드와 경로 값을 넣어주고, 하나씩 heappop 해주면서 heappop으로 뽑아낸 노드가 가진 경로 값과 다른 경로를 통해 해당 노드로 이동할 때의 경로 값을 비교해줘서 작은 값을 distance [현재 노드]에 갱신해주는 방식으로 구현했다.

import sys import heapq input = sys.stdin.readline INF = 100000000 V,e = map(int, input().split()) start = int(input()) data = [[] for _ in range(V+1)] for _ in range(e): u, v, w = map(int, input().split()) data[u].append((v, w)) distance = [INF]*(V+1) q = [] def dijkstra(start): distance[start] = 0 heapq.heappush(q,(0,start)) while q: # print(q) # print(data) # print(distance) dist, now_node = heapq.heappop(q) for n_n, weight in data[now_node]: cost = dist + weight if cost < distance[n_n]: distance[n_n] = cost heapq.heappush(q,(cost,n_n)) dijkstra(start) for i in distance[1:]: if i != INF: print(i) else: print("INF")

from http://resilient-923.tistory.com/335 by ccl(A) rewrite - 2021-08-21 18:00:47