꺼내먹는지식 준
최단 경로 - 다익스트라 본문
개요
최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.
다양한 유형 및 상황에 적절한 효율적인 알고리즘이 이미 정립되어 있다.
- 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우
최단 경로 문제는 보통 그래프로 표현
- 각 지점: 노드
- 지점간 연결된 도로: 간선
보통 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하는 유형이 빈번하게 등장
보통 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 등장하는데, 이 중 벨만 포드는 자주 등장하지 않아 해당 글에서 다루지 않는다.
다익스트라
여러개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
다만 최단 경로 알고리즘은 '음의 간선' 이 없어야 한다. 다만, 현실 세계의 길은 음의 간선이 존재하지 않는다. (GPS의 기본 알고리즘)
다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류한다.
가장 비용이 적은 노드를 선택하고 임의의 과정을 반복한다.
- 1. 출발 노드를 설정
- 2. 최단 거리 테이블을 초기화
- 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
- 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 5. 위 과정에서 3, 4 를 반복
다익스트라 알고리즘은 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하고 계속 갱신한다. (매번 현재 처리하는 노드를 기준으로 주변 간선을 확인한다.)
현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 최단 경로를 갱신한다.
$\rightarrow$ 그리디 알고리즘과 같은 철학
(다익스트라 한줄 정리: 다익스트라는 한 점으로부터 타겟 점까지의 경로 혹은 최단 거리를 구하는 문제. 시작점에서 연결 된 노드로의 거리 업데이트 후, 모든 노드 연결 거리 중 가장 가까운 노드로 이동하여 반복. 가장 가까운 노드로 이동해야 최단 거리를 유지하면서 업데이트 가능하다.)
구현 방법은 다음 2가지 이다.
1) 구현하기 쉽지만 느린 코드
2) 구현하기 조금 더 까다롭지만 빠르게 동작하는 코드
1번 노드에서 다른 모든 노드로의 최단 거리 계산
첫 시작 노드를 1로 지정한다. 1번 노드에서 1번 노드까지의 거리는 0이므로 0으로 설정한다.
1번까지는 0이고, 1번을 거쳐 2,3,4 번 노드로 가는 최소 비용은 각각 2(0+2), 5(0+5), 1(0+1) 이다. 각 값은 새로운 값으로 갱신된다.
이 중 최단 거리가 가장 짧은 노드를 선택한다. 여기서는 min(2, 5, 1) = 1 즉, 4번 노드이다. 4번 노드에서는 3번과 5번으로 이동할 수 있다. 각각 4(1+3), 2(1+1) 이다. 기존 3으로 이동하는 거리는 5인 것에 반해 새로 구한 거리는 4이므로 갱신하고, 5는 처음 거리를 구했으므로 2로 갱신한다.
1, 4번은 모두 방문한 노드이다.
방문 안한 노드 중, 거리가 2로 가장 가까운 노드는 2, 5번 노드이다. 일반적으로 거리가 가까울 때 노드번호가 더 낮은 번호를 선택한다.
2번 노드까지의 거리는 2이다. 2를 기반으로 2번 노드와 연결된 3, 4번 노드로 이동하는 거리는 5(2+3), 4(2+2) 이다. 기존 거리가 더 짧으므로 초기화 되지 않는다.
다음은 5번 노드이다.
5번 노드까지의 거리는 2이므로, 5번 노드를 통해 도달할 수 있는 3, 6번 노드로 이동하는 거리는 3(2+1), 4(2+2) 이다. 3번 노드까지의 거리가 4에서 3으로 갱신되고 6번 노드까지의 거리가 4로 갱신된다.
그 다음으로 방문 안한 노드중 가장 짧은 3번에 방문한다. 3번 노드를 통한 2,6 번 노드까지의 거리는 2(3+3), 8(3+5) 로 갱신은 없다.
위 [Step 1 - Step5]사진 출처: https://velog.io/@hwaya2828/2021-%EC%9D%B4%EC%BD%94%ED%85%8C-7.-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
마지막으로 6번 노드를 선택한 후, 6번 노드를 통해 갈 수 있는 노드는 없으므로 마무리된다.
위 과정은 1번 노드에서 출발하여 2,3,4,5,6 번 노드에 도달하는 최단 거리를 구하는 방법이다.
위 과정을 코드로 옮겨서 구현하면 알고리즘의 복잡도가 $O(V^2)$ 의 시간 복잡도를 가진다. V 는 노드의 수이다.
다익스트라는 최단 경로를 구하는 알고리즘이지만, 주로 거리를 물어보는 문제가 출제되므로 최단 거리를 구하는 형태로 많이 구현하게 된다.
입력 예시
6 11 (Node, 간선)
1 (시작 Node 번호)
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
출력
0 2 3 1 2 4
import sys
input = sys.stdin.readline
INF = 1e9
N, E = map(int,input().split())
start = int(input())
graph = [[] for i in range(N+1)]
visited = [0] * (N+1)
dist = [INF] * (N+1)
for i in range(E):
s,e,d = map(int, input().split())
graph[s].append((e,d))
def update(graph, new):
if visited[new] == 1:
return
#작은거로 초기화
for node in graph[new]:
e, d = node
if dist[e] > d + dist[new]:
dist[e] = d + dist[new]
visited[new] = 1
tmp = 1e9
for i, n in enumerate(dist[1:]):
print("visited", visited)
if visited[i+1] == 1:
continue
if tmp > n:
tmp = n
new = i+1
update(graph, new)
def dijkstra():
dist[start] = 0
update(graph, start)
print(dist)
#print("visited", visited)
dijkstra()코드 참고 없이 직접 구현한 코드
- 1. 첫 시작 노드(s)와 연결된 노드(e)들을 기준으로 최단 거리 갱신,
- 2. 최단 거리 갱신을 마친 후, 노드(s) 방문처리.
- 3. 갱신 된 최단 거리 노드들 중 방문 하지 않았으면서 가장 짧은 노드 선택
- 4. 판단 된 최신 노드도 방문이 완료된 노드일 때 까지 1,2,3 반복
제공된 정답 코드와 내 구현상의 차이
실제 구현은
- 3. 갱신 된 최단 거리 노드들 중 방문 하지 않았으면서 가장 짧은 노드 선택
- 2. 최단 거리 갱신을 마친 후, 노드(s) 방문처리.
순으로 구현 되었고, 재귀 함수가 아닌 for 문으로 구현되었다.
실제 구현은 나와 순서가 다르기에 시작 노드에 대한 최단 거리는 먼저 선으로 업데이트 한다.
구현상 내가 한 구현이 좀 더 readability 가 높고 짧으나 정답 코드가 구현이 더 쉽고 실수할 여지가 적다.
장단점이 있는 듯 하다.
그러나 위 방법은 최단 거리를 조회할 때 모든 노드를 탐색하므로 시간 복잡도가 $O(V^2)$ 이다. 그러나 개선된 방법은 최악의 경우에도 시간 복잡도를 $O(E \log V)$ 를 보장하여 해결 가능하다.
V 는 노드의 개수이고 E 는 간선의 개수이다.
직관적으로 생각해 봤을 때 최단 거리를 모두 탐색한 다는 것은 비효율적이다. 힙 자료구조를 사용하여 특정 노드까지의 최단 거리에 대한 정보를 선형 시간보다 더 빠르게 찾도록 한다.
N = 1,000,000 일 때, $\log_{2} N$ 이 약 20 인 것을 감안하면 속도가 획기적으로 빨라지는 것임을 이해할 수 있다.
우선순위 큐 (효율적인 다익스트라)
스택과 큐에대해서는 다음의 글에서 살펴보았다.
간단하게 정리하자면 아래 표와 같다.
| 자료구조 | 추출 되는 데이터 |
| 스택 | 가장 나중에 삽입한 데이터 |
| 큐 | 가장 먼저 삽입한 데이터 |
| 우선순위 큐 | 가장 우선순위가 높은 데이터 |
우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.
예로, 여러개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내 확인할 때 유용하다.
실제로 코딩테스트에서 힙을 구현할 일은 없다.
from collections import heapq
우선 순위 값을 표현할 때는 일반적으로 정수형 자료형 변수가 사용된다.
우선 순위 큐의 두가지 유형
- 최소 힙: 값이 낮은 데이터가 먼저 삭제
- 최대 힙: 값이 큰 데이터가 먼저 삭제
파이썬 라이브러리는 최소 힙을 기반으로 작성되었고, 혹여나 최대 힙이 필요한 경우에는 값에 음수 부호를 붙여서 최소 힙에 넣고, 추후 데이터를 우선순위 큐에서 빼내고 나면 음수 부호를 다시 붙여 원하는 값을 찾는 방식으로 구현된다.
※ 구현상의 유의점: 튜플을 입력 받으면 첫 번째 원소를 기준으로 우선순위 큐를 구성한다.
| 우선 순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
| 리스트 | $O(1)$ | $O(N)$ |
| 힙(HEAP) | $O( \log N)$ | $O( \log N)$ |
힙의 동작 방식
우선순위 큐를 사용한 다익스트라의 알고리즘은 굉장히 단순하다.
사실상 바뀌었다고 볼 것도 없는게 기존의 방식을 모두 유지하되 다음의 두가지만 유의하면 된다.
- 기존 최단 거리 저장 list 탐색 과정 생략
- 우선순위 큐에 저장 list에서 매번 갱신되는 최단 거리 삽입
- 삽입되는 최단 거리 노드가 중복되어도 최소 힙에 의하여 거리가 더 큰 것은 뒤로 밀린다.
- 뒤로 밀린 값은 추후 빠져나와도 방문 처리가 되어 있으므로 무시할 수 있다.
해당 내용을 기반으로 다익스트라를 다시 구현해보자.
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
INF = 1e9
N, E = map(int,input().split())
start = int(input())
graph = [[] for i in range(N+1)]
visited = [0] * (N+1)
dist = [INF] * (N+1)
#힙은 별도의 자료구조 사용 필요가 없다.
heap = []
for i in range(E):
s,e,d = map(int, input().split())
graph[s].append((d,e)) # 우선 순위 큐에 넣을거면 다음과 같이 앞쪽에 우선순위에 대상이 되는 값을 넣어야 한다.
def update(graph, heap):
while heap:
print(len(heap))
_ , e = heappop(heap)
print("e", e)
if visited[e] != 1:
visited[e] = 1
for node in graph[e]:
d ,target = node
if dist[target] > dist[e] + d:
dist[target] = dist[e] + d
heappush(heap, (dist[target] ,target))
def dijkstra(start):
dist[start] = 0
heappush(heap, (0, start))
update(graph, heap)
print(dist[1:])
dijkstra(start)queue 는 기본적으로 재귀로 구현하는 것이 어색하다.
해당 부분은 재귀로 구현하는 것이 논리적으로 많이 이상하지는 않지만, 이것보다는 우선순위 queue 가 다 비는 순간까지 동작하도록 하는 것이 자연스럽다.
훨씬 짧고, 실제로 구현도 더 단순하다.
실전 예시
1번
N 개의 회사가 있다.
회사가 서로 연결이 되어 있다면 양 방향으로 연결되어 있고 각 거리는 1 이다.
A 는 K 번 회사를 거쳐 X 번 회사에 도달하려고 한다.
이때 최소 거리를 구하여라. 도달할 수 없으면 -1 을 출력하라.
- 회사의 수 $N$, 경로의 개수 $M$ $1 \leq N, M \leq 100$
- 둘째 줄 ~ $M+1$ 줄: 연결된 두 회사의 번호
- $M+2$ 줄: X, K
입력 예시
5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5
다음의 문제는 1번에 있는 A 가 4를 거쳐 5에 도달하는 최소거리를 구하는 문제이다.
기존 다익스트라는 모든 노드를 거쳐 점차 최적화를 한다.
1번 아이디어)
1에서 4에 도달하는 최적 거리를 다익스트라를 통해 구한 후, 4와 5의 연결 거리를 구한다.
2번 아이디어)
플로이드 워셜로 구하고 인접 행렬에서 (1, 4) + (4, 5) 구하기 (플로이드 워셜)
1번이 더 시간적으로 효율적이나 4,5 의 연결 거리를 구하는 것이 문제이다.
이는 4에서의 다익스트라를 다시 구하고 나면 5까지의 최단 거리를 구할 수 있다.
$O(N^3)$ 보다는 $O(N^2 + N^2) \rightarrow O(N^2)$ 이 낫다.
실제 답안을 살펴보면 플로이드 워셜을 쓰는 것을 추천하고 있다.
하지만, 다익스트라로 구현하는 것이 더 바람직할 것이다.
N 이 100 이하이기에 플로이드 워셜로도 풀 수 있는 문제이다.
플로이드 워셜로도 문제를 풀어보자.
2번
N개의 도시가 있다. 각 도시는 일방 통행의 통로만 설치되어 있다. 즉, A에서 B를 가는 통로가 있다는 것이 B에서 A 로 오는 통로가 있는 것은 아니다. 각 통로는 일정 시간이 소요된다.
C 도시에서 메세지를 보낸 다고 할 때 총 몇개의 도시가 메세지를 받으며 소요 시간은 어떻게 되는가?
입력
- 1번 줄: 도시의 개수 N, 통로의 개수 M, 도시 C
- $1 \leq N \leq 30,000, 1 \leq M \leq 200,000, 1 \leq C \leq N$
- 2번 줄 ~ $M+1$ 줄: 통로 $X, Y, Z$($X$에서 $Y$로 $Z$ 시간 동안)
- $1 \leq X, Y \leq N, 1 \leq Z \leq 1,000$
입력 예시
3 2 1
1 2 4
1 3 2출력 예시
2 4
문제가 상당히 직관적이다. 특정 도시를 시작점으로 잡고 각 노드에 도착하는 최소 경로 distance 를 구한다.
총 몇개의 노드에 도착했는지, 그리고 그때 최대 시간은 얼마인지 확인하면 무리가 없다.
구현 코드
import sys
input = sys.stdin.readline
import heapq
INF = 1e9
N, M, C = map(int, input().split())
visited = [0] * (N+1)
graph = [[] for i in range(N+1)]
dist = [INF] * (N+1)
heap = []
for i in range(M):
s, e, d = map(int, input().split())
graph[s].append((e, d))
def update(heap, visited):
while heap:
_, node = heapq.heappop(heap)
if visited[node] != 1:
visited[node] = 1
for n,d in graph[node]:
if dist[n] > dist[node] + d:
dist[n] = dist[node] + d
heapq.heappush(heap, (dist[n], n))
def dijkstra(start):
visited[start] = 1
for n, d in graph[start]:
dist[n] = d
heapq.heappush(heap, (d, n))
update(heap, visited)
dijkstra(C)
cnt = 0
distance = 0
tmp = [i for i in dist[1:] if i < INF]
print(len(tmp), max(tmp))'코딩테스트총정리' 카테고리의 다른 글
| 그래프 이론 - Union, 크루스칼 알고리즘, 위상 정렬 (0) | 2022.08.16 |
|---|---|
| 최단 경로 - 플로이드 워셜 알고리즘 (0) | 2022.08.14 |
| 다이나믹 프로그래밍 (0) | 2022.08.10 |
| 탐색 (순차, 이진) (0) | 2022.08.06 |
| 정렬 (0) | 2022.08.03 |
