고정 헤더 영역
상세 컨텐츠
본문
최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다.
이 책에서는 다익스트라, 프로이드 워셜 알고리즘이 빈도수가 높아 그 두개의 유형을 다룬다.
다익스트라 최단 경로 알고리즘
그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 방법.
음의 간선이 없을 때 정상적으로 동작.
음의 간선이란 0보다 작은 값을 가지는 간선을 의미.
원리는 다음과 같다.
1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3과 4번을 반복한다.
1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.
구현하는 방법은 2가지이다.
방법 1. 구현하기 쉽지만 느리게 동작하는 코드
방법 2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드
방법을 보기 전 다익스트라 알고리즘을 알아보자.
아래 예시를 보자
Step 0. 초기 상태에서는 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화한다. 999,999,999 등의 값으로 설정할 수 있다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
Step 1. 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 즉, 1번 노드와 연결된 모든 간선을 하나씩 확인하면 된다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | 무한 | 무한 |
Step 2. 모든 단계에서도 마찬가지로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야한다.
위의 표를 본다면 4번의 거리가 1이기 때문에 4번 노드를 선택한다. 그리고 4번노드에서 갈 수 있는 노드는 3번과 5번이다.
이때 4번 노드까지의 최단거리는 1이므로 4번 노드에서 갈 수 있는 3번과 5번 노드의 최소비용은 4와 2가 된다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
Step 3. 2번 노드가 선택된다. 2번과 5번 노드까지의 최단 거리가 2로 값이 같은데, 이럴 때는 일반적으로 번호가 작은 노드를 선택한다. 그리고 2번 노드를 거쳐서 도달할 수 있는 노드 중에서 거리가 더 짧은 경우가 있는지 확인한다. 이번 단계에서 2번 노드를 거쳐서 가는 경우, 현재의 최단 거리를 더 짧게 갱신할 수 있는 방법은 없다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
Step 4. 이번에는 5번 노드가 선택된다. 5번 노드를 거쳐 3번과 6번노드를 갈 수 있다. 현재 5번 노드까지 가는 최단 거리가 2이므로 5번 노드에서 3번 노드로 가는 거리인 1을 더한 3이 기존 값인 4보다 작기 때문에 새로운 값 3으로 갱신된다. 또한 6번 노드로 가는 거리도 마찬가지로 4로 갱신된다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
Step 5. 이어서 3번 노드를 선택한 뒤에 동일한 과정을 반복한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
Step 6. 6번 노드를 선택한 후 같은 과정을 반복한다. 지금까지의 최종 최단 거리 테이블은 다음과 같다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.
방법 1. 간단한 다익스트라 알고리즘
간단한 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가진다. (V는 노드의 개수)
단계마다 "방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)한다.
import sys
input = sys.stdin.readline
INF = int(1e9)
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (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))
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
min_value = INF
index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
for i in range(1, n + 1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
# 시작 노드에 대해서 초기화
distance[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
# 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for i in range(n-1):
# 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방무 처리
now = get_smallest_node()
visited[now] = True
# 현재 노드와 연결된 다른 노드를 확인
for j in graph[now]:
cost = distance[now] + j[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[j[0]]:
distance[j[0]] = cost
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])아래 입력을 넣었을때,
6 11
1
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
나오는 결과이다.
노드의 개수 및 간석의 개수가 많을 떄는 개선된 다익스트라 알고리즘을 이용해야한다.
방법 2. 개선된 다익스트라 알고리즘
시간복잡도 O(ElogV)를 보장(E는 간선의 개수, V는 노드의 개수)
방법 2를 사용하기전에 힙에 대한 설명을알아야한다.
힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조이다.
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징인데, 스택과 큐의 삭제방식과 다르다.
파이썬에서 PriorityQueue보다 heapq가 더 빠르게 동작하니 heapq를 쓰자.
힙의 삽입시간은 O(logN), 삭제시간은 O(logN)
현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위큐(힙큐)를 추가로 이용하자.
개선된 알고리즘으로 같은 예시를 접근해보자.
Step 0. 초기 상태에서는 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화한다. 999,999,999 등의 값으로 설정할 수 있다.
개선된 알고리즘은 우선순위 큐도 요구한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
| 우선순위 큐 | (거리 : 0, 노드 : 1) |
Step 1. 거리가 가장 짧은 노드를 선택하기 위해서는 우선순위 큐에서 그냥 노드를 꺼내면 된다. 기본적으로 거리가 짧은 원소가 우선순위 큐의 최상위 원소로 위치해 있다. 따라서 우선순위 큐에서 노드를 꺼낸 뒤에 해당 노드를 이미 처리한 적이 있다면 무시, 아직 처리하지 않은 노드에 대해서만 처리하면 된다. 아래 표에서 거리가 1번 노드가 갈 수 있는 노드들이 거리가 각각 2, 5, 1이다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | 무한 | 무한 |
| 우선순위 큐 | (거리 : 1, 노드 : 4) (거리 : 2, 노드 : 2) (거리 : 5, 노드 : 3) |
앞에서 했던 예시대로 반복한다.
Step 2.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
| 우선순위 큐 | (거리 : 2, 노드 : 2) (거리 : 2, 노드 : 5)(거리 : 4, 노드 : 3)(거리 : 5, 노드 : 3) |
Step 3.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
| 우선순위 큐 | (거리 : 2, 노드 : 5)(거리 : 4, 노드 : 3)(거리 : 5, 노드 : 3) |
Step 4.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리 : 3, 노드 : 3)(거리 : 4, 노드 : 3)(거리 : 4, 노드 : 6)(거리 : 5, 노드 : 3) |
Step 5.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리 : 4, 노드 : 3)(거리 : 4, 노드 : 6)(거리 : 5, 노드 : 3) |
Step 6. 처리된 노드 제거
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리 : 4, 노드 : 6)(거리 : 5, 노드 : 3) |
Step 7.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리 : 5, 노드 : 3) |
Step 8. 처리된 노드 제거
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 |
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n+1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기 하지만 필요없음
# visited = [False] * (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))
def dijkstra(start):
q = []
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):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])아래 입력을 넣었을때,
6 11
1
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
나오는 결과이다.
소스코드만 잘 기억해두자.
플로이드 워셜 알고리즘
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다.
1번노드에서 3번노드까지 가는 최소한의 거리를 바로 예시로 살펴보자.
Step 0.
| 출발 / 도착 | 1번 | 2번 | 3번 | 4번 |
| 1번 | 0 | 4 | 무한 | 6 |
| 2번 | 3 | 0 | 7 | 무한 |
| 3번 | 5 | 무한 | 0 | 4 |
| 4번 | 무한 | 무한 | 2 | 0 |
Step 1. 단순히 1번 노드를 거쳐 가는 경우를 고려한다. 이때는 정확히 다음과 같이 3P2(순열) = 6가지 경우에 대해서만 고민.
2차원 테이블에서는 지워놓았는데, 계산해야 되는 경우의수를 계산한다.
| 0 | 4 | 무한 | 6 |
| 3 | 0 | ||
| 5 | 0 | ||
| 무한 | 0 |
Step 2. 마찬가지로 수행한다.
| 0 | 4 | 무한 | 6 |
| 3 | 0 | 7 | 9 |
| 5 | 9 | 0 | 4 |
| 무한 | 무한 | 2 | 0 |
| 0 | 4 | ||
| 3 | 0 | 7 | 9 |
| 9 | 0 | ||
| 무한 | 0 |
| 0 | 4 | 11 | 6 |
| 3 | 0 | 7 | 9 |
| 5 | 9 | 0 | 4 |
| 무한 | 무한 | 2 | 0 |
Step 3. 마찬가지로 수행한다.
| 0 | 4 | 11 | 6 |
| 3 | 0 | 7 | 9 |
| 5 | 9 | 0 | 4 |
| 무한 | 무한 | 2 | 0 |
| 0 | 11 | ||
| 0 | 7 | ||
| 5 | 9 | 0 | 4 |
| 2 | 0 |
| 0 | 4 | 11 | 6 |
| 3 | 0 | 7 | 9 |
| 5 | 9 | 0 | 4 |
| 7 | 11 | 2 | 0 |
Step 4. 마찬가지로 수행한다.
| 0 | 4 | 11 | 6 |
| 3 | 0 | 7 | 9 |
| 5 | 9 | 0 | 4 |
| 7 | 11 | 2 | 0 |
| 0 | 6 | ||
| 0 | 9 | ||
| 0 | 4 | ||
| 7 | 11 | 2 | 0 |
| 0 | 4 | 8 | 6 |
| 3 | 0 | 7 | 9 |
| 5 | 9 | 0 | 4 |
| 7 | 11 | 2 | 0 |
이렇게 해서 1번 노드에서 3번노드까지 가는 최단거리는 8이다.
예제 코드이다.
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 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):
# 도달할 수 없는 경우, 무한이라고 출력
if graph[a][b] == INF:
print("INFINITY", end=" ")
# 도달할 수 있는 경우 거리를 출력
else:
print(graph[a][b], end = " ")
print()
예제문제 1. 미래 도시
방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력하는 문제이다.
도달할 수 없다면 -1을 출력
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n + 1) for _ in range(n+1)]
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
# 각 간선에 대한 정보
for _ in range(m):
# A와 B가 서로에게 가는 비용은 1이라고 설정
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
# 거쳐 갈 노드 X와 최종 목적지 노드 K를 입력받기
x, k = map(int, input().split())
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])
distance = graph[1][k] + graph[k][x]
if distance >= INF:
print("-1")
else:
print(distance)
연습문제 2. 전보
도시 C에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m, start = map(int, input().split())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
x, y, z = map(int, input().split())
graph[x].append((y, z))
def dijkstra(start):
q = []
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)
count = 0
max_distance = 0
for d in distance:
if d != INF:
count += 1
max_distance = max(max_distance, d)
print(count - 1, max_distance)'책 리뷰 > 이것이 취업을 위한 코딩테스트다' 카테고리의 다른 글
| 10일차 - 그래프 이론 (1) | 2024.01.09 |
|---|---|
| 6일차 - 다이나믹 프로그래밍 (3) | 2024.01.04 |
| 5일차 - 이진 탐색 (1) | 2024.01.03 |
| 4일차 - 정렬 (0) | 2024.01.02 |
| 3일차 - DFS/BFS (1) | 2023.12.27 |
댓글 영역