알고리즘 유형 : 다익스트라(dijkstra)
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/1753
소스 코드(파이썬)
import heapq
import sys
input = sys.stdin.readline
V, E = map(int, input().split())
start = int(input())
graph = [[] for _ in range(V+1)]
# 그래프 정보 저장
for _ in range(E):
u, v, w = map(int, input().split())
graph[u].append((v, w))
# 다익스트라 알고리즘
def dijkstra(start):
distances = [float("inf")]*(V+1)
distances[start] = 0
q = []
# 힙은 새 기준이 될, 방문했던 인접 노드들 중 그 노드까지의 최단 거리가 가장 짧은 것을 먼저 방문하기 위해 씀
heapq.heappush(q, (distances[start], start))
while q:
cnt_distance, node = heapq.heappop(q)
# BFS처럼 수행하기에, 한 level에서 특정 인접 노드에 대한 정보가 중복될 수 있음
# 만약 (2, 4)가 이미 distances에 있는데, (2, 7)을 힙에서 뽑았다면,
# 최단거리인 4를 활용하는게 맞으므로 (2, 7)은 그냥 넘어간다.
if distances[node] < cnt_distance:
continue
# 인접 노드들 중에 최단거리 갱신이 되는 노드들은 갱신해주고, 갱신 안했으면
# 그냥 힙에 안넣고 넘어가면 됨. 이미 더 짧은 최단거리가 존재하고 있다는 것은
# 다른 경로로 이 노드를 방문하는 경우가 존재한다는 것이므로 그 경우에서
# 어차피 처리해줄 것이기 때문
for adjacency_node, distance in graph[node]:
cal_distance = distances[node] + distance
if cal_distance < distances[adjacency_node]:
distances[adjacency_node] = cal_distance
heapq.heappush(q, (cal_distance, adjacency_node))
return distances
result = dijkstra(start)
for i in range(1, len(result)):
print("INF" if result[i] == float("inf") else result[i])풀이 요약
- 다익스트라 알고리즘을 활용하는 전형적인 문제이다.
-
그래프 리스트에 들어온 입력들을 저장해준다.
그래프는 2차원 배열로 초기화되고, 첫 번째 인덱싱 요소들은 출발 노드, 그 인덱스의 요소 리스트는 튜플이 들어있는데, (도착 노드, 가중치)의 형태로 저장한다.
이 때 그래프 리스트의 출발 노드 인덱스들은 반드시 모든 노드들에 대해 존재해야한다.
만약 어떤 노드가 자신이 출발 노드고 다른 임의의 노드로 가는 간선이 없더라도, 그 노드의 두 번째 요소 리스트는 빈 리스트로 존재해야한다.
왜냐하면 다익스트라는 모든 간선을 탐색하기 때문에 모든 노드를 넣었다 빼고, 그 과정에서 for문을 돌 때 graph[node]를 조회하기 때문에 인덱싱 오류를 피하기 위해 빈 리스트라도 초기화해두는 것이다.
다익스트라는 모든 노드까지의 최단 거리를 구하므로 당연히 distances 리스트도 모든 노드에 대해 초기화가 되어있어야한다.
-
그 외에는 다익스트라 알고리즘을 그대로 구현하면 된다.
처음 출발 노드의 최단 거리를 0으로 초기화하고, 나머지는 갱신을 위해 최대값으로 초기화해둔다.
힙에 첫 출발 노드를 넣어두고, 인접 노드를 계속 탐색해나가면서 그 노드의 최단 거리를 계속 갱신해나간다.
특정 노드의 최단거리를 그 이전의 노드의 최단거리를 활용하여 구하므로 DP의 성격을 띠고, 바텀업 방식으로 탐색하며 그 방식이 greedy의 성격도 띤다.
첫 출발 노드로부터 인접 노드들에 대해 탐색하는 과정을 밝기에 BFS의 구조를 갖고, 이 때 갱신하고나서 인접 노드들 중 새로 기준이 될 노드는 최단 거리가 가장 작은 것으로 고른다.
그 이유는, https://brownbears.tistory.com/554
이 블로그에서 제공하는 예제에서 B로 먼저 가버리면 B는 최단 거리가 10인채로 끝나게 되는데, C로 먼저 가면 이 경우 C를 거쳐서 B로 가는 최단 거리 7이 존재하기 때문에 B를 최단으로 갱신해줄 수 있다. 이런 경우의 수를 고려해준 것이다.
배운 점, 어려웠던 점
- 다익스트라 알고리즘을 배우고 적용해볼 수 있는 유익한 문제였다.
