💻코딩테스트
[이코테_코딩테스트] 최단 경로 알고리즘 - 2
- 어떻게 해야 다익스트라 알고리즘이 더 효율적으로 동작할 수 있을까?
우선순위 큐 (Priority Queue)
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
- 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 우선순위 큐를 이용할 수 있다.
- Python, C++, Java를 포함한 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F48e78914-2425-4d25-b6d8-30fcd17a8c8f%2FUntitled.png?table=block&id=6721b2d8-7f0d-4313-b999-7649ce07cbb6&cache=v2)
힙(Heap)
- 우선순위 큐를 구현하기 위해 사용되는 자료구조 중 하나
- 최소 힙 (Min Heap)과 최대 힙 (Max Heap)이 있다.
- 다익스트라 최단 경로 알고리즘을 포함한 다양한 알고리즘에 사용된다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F93aa4578-d793-4ba7-8e5d-3a14a5eb5a02%2FUntitled.png?table=block&id=067387bc-591a-444b-9f71-6cee95b68a0b&cache=v2)
힙 라이브러리 사용 예제 - 최소 힙
import heapq # 오름차순 힙 정렬 def heapsort(iterable): h = [] result = [] # 모든 원소 차례대로 힙에 삽입 for value in iterable: heapq.heappush(h, value) # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 # 기본 heap 라이브러리는 min heap 방식 for i in range(len(h)): result.append(heapq.heappop(h)) return result result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) print(result)
힙 라이브러리 사용 예제 - 최대 힙
import heapq # 오름차순 힙 정렬 def heapsort(iterable): h = [] result = [] # 모든 원소 차례대로 힙에 삽입 for value in iterable: heapq.heappush(h, -value) # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 for i in range(len(h)): result.append(-heapq.heappop(h)) return result result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) print(result)
- heap에 넣을 때 부호를 변경해서 입력한 뒤, 꺼낼 때 부호를 변경해서 꺼낸다.
다익스트라 알고리즘 - 개선된 구현 방법
- 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조를 이용
- 다익스트라 알고리즘이 동작하는 기본 원리는 동일하다.
- 현재 가장 가까운 노드를 저장해 놓기 위해 힙 자료구조를 추가적으로 이용한다는 점이 다르다.
- 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용
다익스트라 알고리즘 - 동작 과정 (우선순위 큐)
[초기 상태] 그래프 준비하고 출발 노드를 설정하여 우선순위 큐에 삽입
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fed1849f3-26b3-4ea0-bdce-358b01386243%2FUntitled.png?table=block&id=59a8420c-0d01-4de3-add4-dd3b7c743b66&cache=v2)
[Step 1] 우선순위 큐에서 원소를 꺼낸다. 1번 노드는 아직 방문하지 않았으니 이를 처리한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F982a0bcf-f2b7-4a39-83a8-1f70295ebaed%2FUntitled.png?table=block&id=5fe5e005-e972-4304-a9e8-4476e6187ac7&cache=v2)
[Step 2] 우선순위 큐에서 원소를 꺼낸다. 4번 노드는 아직 방문하지 않았으니 이를 처리한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F72059ffd-13c5-45da-985d-c0c5d2730658%2FUntitled.png?table=block&id=41bcc450-b133-433c-b446-1981ee38a667&cache=v2)
[Step 3] 우선순위 큐에서 원소를 꺼낸다. 2번 노드는 아직 방문하지 않았으니 이를 처리한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fe693539b-8ac4-45af-b825-5c6779b08773%2FUntitled.png?table=block&id=f76df0a5-8aa8-4675-9312-8fd3e3dd3f1f&cache=v2)
[Step 4] 우선순위 큐에서 원소를 꺼낸다. 5번 노드는 아직 방문하지 않았으니 이를 처리한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fd207d3ab-e10f-4246-990f-d2f94be073dc%2FUntitled.png?table=block&id=75fdcd4c-877f-4680-b842-fac2a78cfb7a&cache=v2)
[Step 5] 우선순위 큐에서 원소를 꺼낸다. 3번 노드는 아직 방문하지 않았으니 이를 처리한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F0c3cb91a-6a77-407b-9518-63ffb1b44b2a%2FUntitled.png?table=block&id=e3c61664-994f-48bd-bfcf-bce64d6b3f05&cache=v2)
[Step 6] 우선순위 큐에서 원소를 꺼낸다. 3번 노드는 이미 방문했으므로 무시한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F909a06fb-5c81-4e0d-b441-022f20d98371%2FUntitled.png?table=block&id=d3d16bc7-ea09-444b-a1fb-4dd3fd28ba23&cache=v2)
[Step 7] 우선순위 큐에서 원소를 꺼낸다. 6번 노드는 아직 방문하지 않았으니 이를 처리한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F6792d045-4657-4856-8cd2-aa0249b35b66%2FUntitled.png?table=block&id=efb6b4bd-821f-461b-b84c-73931e2f6676&cache=v2)
[Step 8] 우선순위 큐에서 원소를 꺼낸다. 3번 노드는 이미 방문했으므로 무시한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F30d9d952-55d8-416b-934f-2dab5216bc11%2FUntitled.png?table=block&id=07351401-e560-4835-bfc1-b92243913d1f&cache=v2)
다익스트라 알고리즘 - 개선된 구현 방법 (Python)
import heapq import sys input = sys.stdin.readline INF = int(1e9) # 무한 값 의미로 10억 설정 # 노드와 간선의 개수 입력받기 n, m = map(int, input().split()) # 시작 노드 번호 입력받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보 담는 리스트 graph = [[] for i in range(n + 1)] # 최단 거리 테이블 초기화 distance = [INF] * (n + 1) # 모든 간선 정보 입력받기 for _ in range(m): a, b, c = map(int, input().split()) # a번 노드에서 b번 노드로 가는 비용은 c이다. graph[a].append((b, c)) """ 이 부분까지는 앞에서 한 다익스트라 알고리즘 구현 방식과 똑같음 방문 처리 목적인 visited, 최단 거리 구하는 get_smallest_node() 사용하지 않음 """ def dijkstra(start): q = [] # 시작 노드로 가기 위한 최단 경로 -> 0으로 설정, 우선수위 큐에 삽입 heapq.heappush(q, (0, start)) distance[start] = 0 # 우선순위 큐 빌 때까지 반복 while q: # 최단 거리 짧은 노드 꺼내기 dist, now = heapq.heappop(q) # 현재 노드가 이미 처리된 적이 있다면 무시한다. if distance[now] < dist: continue # 현재 노드와 연결된 다른 인접 노드 확인 for i in graph[now]: cost = dist + i[1] # 최단 거리 갱신되는 경우 if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) # 다익스트라 알고리즘 수행 dijkstra(start) # 모든 노드로 가기 위한 최단 거리 출력 for i in range(1, n + 1): if distance[i] == INF: print("INF") else: print(distance[i])
다익스트라 알고리즘 - 개선된 구현 방법 성능 분석
- 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는
- 노드를 하나씩 꺼내 검사하는 반복문(while)은 노드의 개수 V 이상의 횟수로 처리되지 않는다.
- 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총횟수는 최대 간선의 개수(E)만큼 연산이 수행될 수 있다.
- 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼는 연산과 매우 유사
- 시간 복잡도를 로 판단할 수 있다.
- 중복 간선을 포함하지 않는 경우 이를 로 정리할 수 있다.
이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘” 영상을 보고 작성하였습니다.