✔ 풀이를 위한 아이디어
- 그래프 (Graph) 이론
- 다익스트라 (Dijkstra) 알고리즘 (한 지점에서 다른 모든 지점까지의 최단 경로)
✔ 알고리즘 설명
다익스트라 알고리즘을 공부한 뒤에 코드를 짜보았다.
https://www.youtube.com/watch?v=F-tkqjUiik0 의 알고리즘 설명부분만 참고하였다.
필요한 데이터 목록
- 노드와 간선 정보가 담긴 그래프 (각 노드에 연결된 지점들과 그에 대응하는 거리 정보)
graph = [[] for _ in range(V+1)]
for _ in range(E):
u, v, w = map(int, sys.stdin.readline().split())
graph[u].append((w, v)) # graph[u]에 index 0이 거리, 1이 지점인 tuple이 여러 개 달려있음- 각 지점까지의 최소 거리에 대한 정보가 담긴 테이블 (모두 무한 값으로 초기화)
table = [INF]*(V+1)- 방문하지 않은 노드 중에서, 최단거리가 가장 짧은 노드를 반환하는 우선순위 큐 (최소 힙)
우선순위 큐 사용 안 할 때는 시간복잡도가 O(N), 사용 할 때는 O(logN) <- 사용 해야함
table[start] = 0 # 시작점의 table은 0으로 초기화 (나부터 나까지의 거리는 0이므로)
heap = [(table[start], start)]
# heap에도 역시 index 0이 거리, 1이 지점인 tuple이 여러 개 달려 있음
# table 정보를 갱신할 때마다 heap에 넣어줌 (갱신한 지점과, 현재의 그 지점까지의 최소 거리) 핵심 알고리즘
def dijkstra():
while heap:
tmp = heapq.heappop(heap) # (거리, 지점) tuple로 구성된 현재 처리 중인 노드 정보
if table[tmp[1]] < tmp[0]: # 이미 있는 값이 더 작다면, 갱신 완료 한 것이므로 건너 뜀
continue # (5, 3) -> (4, 3) 순서로 들어가도 (4, 3) 이 먼저 나와서 남은 것
for i in range(len(graph[tmp[1]])): # graph 뒤에 달려 있는 tuple의 개수만큼 반복
# 현재 탐색 중인 노드와 연결된 지점들을 검토
current = graph[tmp[1]][i] # 현재 탐색 중인 노드와 연결된 지점들 중
현재 다음 지점으로 고려 중인 노드에 대한 정보가 담긴 tuple
# current는 갈 지점에 대한 정보, tmp는 현재 지점에 대한 정보
if table[tmp[1]] + current[0] < table[current[1]]:
# table[tmp[1]]: 기존에 시작 노드 ~ 현재 탐색 중인 노드 까지의 최소 거리
# current[0]: 현재 탐색 중인 노드 ~ 다음 지점으로 고려 중인 노드 까지의 거리
# table[current[1]]: 기존에 시작 노드 ~ 다음 지점으로 고려 중인 노드 까지의 최소 거리
table[current[1]] = table[tmp[1]] + current[0]
heapq.heappush(heap, (table[current[1]], current[1]))
- 알고리즘은 아래와 같은 순서로 동작한다.
-
방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택 해서 처리 시작
-
해당 노드와 연결 된 지점들을 모두 검토하며, 해당 노드를 거쳐 다른 노드로 가는 거리를 확인하고, 기존의 최단 거리 테이블을 갱신함.
-
테이블을 갱신할 때마다 그 다른 노드에 대한 정보를 힙에 넣어 줌
-
위의 1~3 과정을 반복하며 모든 테이블을 갱신해나간다.
✔ 전체 코드
import sys
import heapq
INF = float('inf') # 무한을 INF로 정의
V, E = map(int, sys.stdin.readline().split())
start = int(input())
graph = [[] for _ in range(V+1)]
for _ in range(E):
u, v, w = map(int, sys.stdin.readline().split())
graph[u].append((w, v))
table = [INF]*(V+1)
table[start] = 0
heap = [(0, start)]
def dijkstra():
while heap:
tmp = heapq.heappop(heap)
if table[tmp[1]] < tmp[0]:
continue
for i in range(len(graph[tmp[1]])):
current = graph[tmp[1]][i]
if table[tmp[1]] + current[0] < table[current[1]]:
table[current[1]] = table[tmp[1]] + current[0]
heapq.heappush(heap, (table[current[1]], current[1]))
dijkstra()
for i in range(1, V+1):
if table[i] == INF: # Python에서 전역 변수로 선언된 리스트는 global 안써도 값이 변함
print("INF") # https://livlikwav.github.io/python/python-mutable-and-namespace/
else:
print(table[i])
꽤나 복잡한 알고리즘이기 때문에 계속 복습하고, 다시 구현해보도록 하자!
- 백준 11779번: 최소비용 구하기 2 - http://boj.kr/280a4ba8af124dea929fe90e7fa82f84
위 문제를 풀면서, 다익스트라 코드 자체가 더 깔끔해진 것 같아서 첨부한다.
