사전 지식 정리
힙 (Heap)
우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제
대부분의 프로그래밍 언어에서 우선순위 큐 라이브러리를 지원
→ 일반적으로 코딩 테스트 환경에서 직접 힙 자료구조부터 작성해서 우선순위 큐를 구현할 일은 없음
종류
- 최소힙
- 값이 낮은 데이터가 먼저 삭제
- 최대힙
- 값이 큰 데이터가 먼저 삭제
파이썬 라이브러리
- PriorityQueue
- heapq (권장)
<aside> 💡 최소힙 ←→ 최대힙 변환 사용 팁
- 부호를 이용해 넣고, 빼고 나서 다시 - 적용
</aside>
최단 경로 (Shortest Path) 알고리즘
정의
- 가장 짧은 경로를 찾는 알고리즘
- ‘길찾기’ 알고리즘이라고도 불림
- 다양한 상황에 맞는 효율적인 알고리즘들이 이미 정립되어 있음
- 최단 거리 주요 알고리즘들은 앞서 공부한 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 적용됨
- 최적 부분 구조를 가짐을 의미
표현 방법
- 그래프
- 각 지점 : 노드
- 각 지점간 연결된 길 : 간선
대표적 최단 거리 알고리즘 3가지
- 벨만 포드
- 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 사용
- 다익스트라 (출제 우세)
- 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 사용
- 그리디 알고리즘
- 플로이드 워셜 (출제 우세)
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용
- 다이나믹 프로그래밍 알고리즘
다익스트라(Dijkstra) 최단 경로 알고리즘
정의
- 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
특징
- 최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신함
- 이러한 리스트를 최단 거리 테이블이라고 함
- 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인
- 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 더 짧은 경로로 판단
- 따라서 ‘방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인’해 그 노드에 대해 최단거리 테이블 갱신을 수행한다는 점에서 그리디 알고리즘으로 볼 수 있음
- 가장 짧은 노드를 확인 방법
- 간단한 알고리즘 : 순차 탐색
- 개선된 알고리즘 : 우선순위 큐 (최소힙)
- 시간 복잡도
- 간단한 알고리즘 : $O(V^2)$ - V:정점 수
- 개선된 알고리즘 : $O(ElogV)$ - E:간선 수, V:정점 수
- 가장 짧은 노드를 확인 방법
- 제약 사항
음의 간선이 없어야 함 → 현실 세계 길에는 존재 하지 않음
→ 그럼 어디에? → 예) 연료의 소비
동작 과정
- 출발 노드를 설정
- 최단 거리 테이블을 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신
- 위 과정에서 3~4 반복
동작 원리 예시
1번 노드에서 다른 노드로 가는 최단 경로는 구하는 경우
초기 테이블 상태 : 다른 노드로 가는 최단 거리는 ‘무한’, 시작 노드는 0으로 설정
- 파이썬 지수 표기법 무한 사용 :
int(1e9)
먼저 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택
→ 처음에는 시작 노드가 0이므로 시작 노드가 선택됨
이제 1번 노드를 거쳐 다른 노드로 가는 비용 계산
→ 1번 노드와 연결된 간선들을 하나씩 확인
- 2로가는 비용 : 0 + 2
- 3으로 가는 비용 : 0 + 5
- 4로 가는 비용 : 0 + 1
이후의 모든 단계에서도 마찬가지로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야 함. 따라서 4번 노드 선택
→ 4번 노드를 거쳐서 3번과 5번 노드로 가는 최소 비용 계산
- 3으로 가는 비용 : 1 + 3
- 5로 가는 비용 : 1 + 1
2번 노드가 선택됨 (2, 5중 번호가 작은 2 선택)
→ 2번 노드를 거쳐 갈 수 있는 노드는 3번 노드 하나
- 3으로 가는 비용 : 2 + 3
5번 노드 선택
→ 거쳐 갈 수 있는 노드 : 3, 6
- 3으로 가는 비용 : 2 + 1
- 6으로 가는 비용 : 2 + 2
3번 노드 선택
→ 거쳐 갈 수 있는 노드 : 2, 6
- 2로 가는 비용 : 3 + 3
- 6으로 가는 비용 : 3 + 5
6번 노드 선택
→ 거쳐 갈 수 있는 노드 없음
→ 이렇게 완성된 최단 거리 테이블이 의미하는 것은 1번 노드로 부터 각 노드까지의 최단 거리임
→ ‘방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택’
→ 이렇게 선택된 노드는 ‘최단 거리’가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않음
→ 한 단계당 하나의 최단 거리를 반드시 찾음
구현 방법
구현하기 쉽지만 느리게 동작하는 코드
간단한 다익스트라 알고리즘
- 시간 복잡도 : $O(V^2)$
- 전체 노드의 수가 5000개 이하 정도의 문제에 적용 가능
- 구현 방식
- 최단 거리 테이블 : 1차원 배열
- 가장 짧은 노드 선택 : 순차 탐색
구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드
개선된 다익스트라 알고리즘
- 시간 복잡도 : $O(ElogV)$
- 구현 방식
- 최단 거리 테이블 : 우선순위 큐 (
heapq) - 가장 짧은 노드 선택 : 우선순위 큐 이용
- 최단 거리 테이블 : 우선순위 큐 (
플로이드 워셜(Floyd-Warshall) 알고리즘
정의
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘
특징
- 소스코드가 매우 짧아서 다익스트라 알고리즘과 비교해 구현 과정이 어렵진 않음
- 다만, 핵심 아이디어 이해 필요
- 다익스트라 알고리즘과 같이 단계마다 ‘거쳐 가는 노드’를 기준으로 알고리즘을 수행
- 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요는 없음
- 노드의 개수가 N개일 때 알고리즘 상으로 N번의 단계를 수행, 단계마다 O(N^2)의 연산을 통해 ‘현재 노드를 거쳐 가는’ 모든 경로를 고려
- 시간 복잡도 : $O(N^3)$
- 2차원 리스트를 이용 → $O(N^2)$
- $O(N^2)$의 과정을 ****N번 수행 → $O(N^3)$
- 시간 복잡도 : $O(N^3)$
- 최단 거리 테이블 : 2차원 리스트 이용
- 모든 노드에 대해 다른 모든 노드로가는 최단 거리 정보를 담아야 하기 때문
- 노드의 개수가 N일 때, N번 만큼의 단계를 반복하며 ‘점화식에 맞게’ 2차원 리스트를 갱신하므로 다이나믹 프로그래밍으로 볼 수 있음
동작 과정
- 각 단계에서는 해당 노드를 거쳐 가는 모든 경우를 고려
- 만약, 1번 노드에 대해서 확인 시 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려
- 정확히는 A → 1번 노드 → B로 가는 비용을 확인한 후에 최단 거리를 갱신
- 예)
- 현재 최단 거리 테이블에 A번 노드에서 B번 노드로 이동하는 비용이 3으로 기록되어 있을 때, A번 노드에서 1번 노드를 거쳐 B번 노드로 이동하는 비용이 2라는 것이 밝혀지면, A번 노드에서 B번 노드로 이동하는 비용을 2로 갱신
- 알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N - 1개의 노드 중에서 서로 다른 노드 (A, B)쌍을 선택
- A → 1번 노드 → B로 가는 비용을 확인한 후 최단 거리를 갱신
- $_{N-1}P_2$ 개의 쌍을 단계마다 반복해서 확인
- 이 때 $O(_{N-1}P_2)$는 $O(N^2)$이라고 볼 수 있음
- 점화식 :
$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$- ‘A에서 B로 가는 최소 비용’과 ‘A에서 K를 거쳐 B로 가는 비용’을 비교해 더 작은 값으로 갱신 의미
동작 원리 예제
초기 테이블 상태
- 연결된 간선 : 해당 값으로 채움
- 연결되지 않은 간선 : 무한 (
int(1e9)) - 자기 자신 : 0
단순히 1번 노드를 거쳐가는 경우 고려
$_3P_2 = 6$ 의 경우에 대해서 고려
- $D_{23} = min(D_{23}, D_{21} + D_{13})$
- $D_{24} = min(D_{24}, D_{21} + D_{14})$
- $D_{32} = min(D_{32}, D_{31} + D_{12})$
- $D_{34} = min(D_{34}, D_{31} + D_{14})$
- $D_{42} = min(D_{42}, D_{41} + D_{12})$
- $D_{43} = min(D_{43}, D_{41} + D_{13})$
위와 같은 방법으로 2번 노드를 거쳐 가는 경우 고려 계산
3번 노드에 대해 반복
4번 노드에 대해 반복
모든 노드에 대해 반복하였으므로 위의 결과가 모든 노드에 대한 최단 경로 테이블임
$D_{13} = 8$: 1번 노드에서 3번 노드로 가는 최단 거리가 8임을 의미
구현
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정
# 노드의 개수 및 간선의 개수 입력
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
graph[a][a] = 0
# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
# A에서 B로 가는 비용은 C라고 설정
a, b, c = map(int, input().split())
graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# 수행된 결과를 출력
for a in range(1, n + 1):
for b in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)으로 출력
if graph[a][b] == INF:
print("INFINITY", end=" ")
# 도달할 수 있는 경우 거리를 출력
else:
print(graph[a][b], end=" ")
print()
그 외 최단 거리 알고리즘
벨만-포드 (Bellman-Ford)
가중치 계산과 변경을 모든 간선에 대해 반복 실행
간선의 가중치가 음수여도 해결 가능
음의 폐로가 존재 유무 확인 가능
- 해당 경로 가중치가 계속 작아지므로 변화가 N회 이상 계속 발생하는 것으로 감지
방향성 그래프와 비방향성 그래프에 모두 적용 가능
N회 수행 시점에 N번 이하 이동할 경우의 최단 거리를 구할 수 있음
- N-1회 작업을 수행하면 모든 정점에 대한 최단 경로를 구할 수 있음
- 모든 정점 테이블의 값이 변경이 없는 경우도 탐색이 끝난 것임
파이썬 의사 코드
def bellman_ford(g, w, s):
INITIALIZE_SINGLE_SOURCE(g, s)
for i in range(1, |g.v| - 1)
for 각 간선 (u, v) in g.e:
RELAX(u, v, w)
for 각 간선 (u, v) in g.e:
if v.d > u.d + w(u.v):
return False
return True
수행 과정 예시
A* (에이 스타)
- 다익스트라 방법을 발전시킨 알고리즘
- 시작점부터의 가중치 뿐만 아니라 현 시점에서 목표까지의 추정 가중치도 함께 고려
- 대략적은 목표 지점의 위치를 알고 있어야 함
- 이 추정 가중치를 발견적 가중치라고 함
- 추정 가중치를 통해 목표 지점에서 멀어지는 탐색을 최소화 할 수 있음
- 현실에서 최단 가중치를 알고 있는 경우는 없음 → 탐색의 필요가 없음
- 게임 프로그래밍에서 적이 플레이어의 움직임을 쫓는 계산 등에 사용
존슨 알고리즘
모든 쌍 최단 경로를 구함
벨만-포드와 다익스트라의 서브 루틴을 이용
가중치 조정 기술 사용
의사 코드
정리
단일 쌍의 최단 경로 알고리즘
- 벨만-포드
- 음의 가중치도 가능
- 음의 폐로 존재 확인 가능
- 다익스트라
- 그리디를 활용해 벨만-포드보다 효율적
- 음의 가중치, 음의 폐로 확인 불가
- 에이스타
- 다익스트라 방법을 발전시킨 알고리즘 → 현실적 사용 불가
- 시작점부터의 가중치 뿐만 아니라 현 시점에서 목표까지의 추정 가중치도 함께 고려
모든 쌍의 최단 경로 알고리즘
- 플로이드 워셜
- 다이나믹 프로그래밍 활용
- 존슨
- 플로이드 워셜보다 점근적으로 더 빠름
- 정점의 모든 쌍의 최소 경로 가중치의 행렬을 리턴하거나 입력 그래프가 음의 가중치를 가지는 순환을 포함함을 알려줌
