[Baekjoon] 1753. 최단경로 [G5]
📚 문제
https://www.acmicpc.net/problem/1753
📖 풀이
플로이드 워셜 알고리즘을 공부하며 봤던 다익스트라 알고리즘이다.
하나의 정점에서 최단 경로를 구할 때 활용한다.
📌 다익스트라 알고리즘 참고 :
다익스트라 알고리즘의 핵심은 정점에서 연결되는 모든 정점을 확인할 것인데 가장 가까운 정점부터 확인한다.
가까운 정점을 들렸다가 다른 정점을 가는 경우가 더 빠르면 그 정점의 값을 바꾸어 준다. 바꾼 후 다시 가까운 정점을 확인해 바꿔주는 걸 반복한다.
배열의 크기가 큰데 인접행렬로 만들면 메모리 초과 발생한다!
따라서 인접리스트로 만들어서 사용해야한다.
다익스트라 알고리즘은 정점을 확인할 때마다 최솟값이 바뀔 수 있어서 최솟값을 계속 확인해줘야 한다. 따라서 힙으로 구현하는 것이 매우 효율적이다.
힙에 노드의 최솟값을 넣어주면 힙에 같은 노드가 여러 개 쌓이는 경우가 생긴다. 정점과의 거리를 계속 변경했으니, 꺼낸 노드와 저장되어있던 노드의 거리가 다르면 이전에 넣어놨던 정점이다. 따라서 꺼낸 후 continue로 힙에서 버리는 작업만 한다.
heap에 남은 노드가 없으면 종료한다.
📒 코드
import heapq
import sys
input = sys.stdin.readline
n, e = map(int, input().split()) # 정점과 간선의 수
INF = n * 10 # 나올 수 있는 가장 큰 값보다 크게 설정
arr = [[] for _ in range(n + 1)]
start = int(input().rstrip()) # 시작점
dp = [0 for _ in range(n + 1)]
for _ in range(e): # 가중치에 관한 그래프
a, b, w = map(int, input().split())
arr[a].append((w, b)) # 행 -> 열 일 때 값은 가중치
dp = [INF for _ in range(n + 1)] # 시작점에서의 최단 거리
dp[start] = 0 # 시작점은 0이다.
heap = []
heapq.heappush(heap, (0, start)) # 시작점을 담고 시작
while heap:
w, v = heapq.heappop(heap)
if dp[v] != w: # 변경된 값과 다르면 pass
continue
for t_w, t_v in arr[v]:
if dp[t_v] > t_w + w: # 최소값으로 넣어준다.
dp[t_v] = t_w + w
heapq.heappush(heap,(t_w + w, t_v))
for i in range(1, n + 1):
print('INF' if dp[i] == INF else dp[i])
🔍 결과
Author And Source
이 문제에 관하여([Baekjoon] 1753. 최단경로 [G5]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/Baekjoon-1753.-최단경로-G5저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)