정점들과 그 사이를 연결하는 간선들이 주어졌을 때, 간선의 가중치가 모두 같다면 BFS(깊이우선탐색)를 활용하여 각 정점간의 최단거리를 구할 수 있다. 이번에는 간선들의 가중치가 서로 다를 때 최단거리를 구하기 위해 사용 가능한 알고리즘 중 하나인 Dijkstra의 알고리즘에 대해 정리해본다
Dijkstra 알고리즘은 동적 계획법을 활용하여 최단경로를 구하는 알고리즘이다. 절차는 다음과 같다
① 먼저 시작점 s로부터의 각 정점까지의 거리를 나타낼 배열 d를 INF(무한)으로 초기화한다.
② d[s]를 0으로 초기화한다 (자기 자신과의 거리는 0이기 때문에)
③ 현 시점에서 가장 s로부터의 거리가 가까운 정점을 경유할 정점 m으로 잡고
그 점을 경유한 최단거리로 d를 갱신한다. ( s -> m -> i == min(d[i], d[m] + graph[m][i]) )
④ ③을 더이상 갱신이 일어나지 않을 때 까지 반복한다.
실제 구현에 있어 주의해야할 부분은 두 가지가 있다. 그래프의 관리방식과 단계③에서 가장 가까운 경유점을 찾는 방식이다.
그래프의 경우 단순히 n * n 배열로 관리하게될 경우 인접 정점을 찾기위해 매번 n-1회의 탐색이 필요하다(O(n)) 이를 해결하려면 그래프를 각 정점의 인접 정점들의 집합을 요소로 가지도록 하면 된다.
INF = float('inf')
g1 = [
[0, 1, INF, 1],
[1, 0, 1, INF],
[INF, 1, 0, 1],
[1, INF, 1, 0]
]
g2 = [
[1, 3],
[0, 2],
[1, 3],
[0, 2]
]g1과 같이 그래프는 관리하는것 보다 g2와 같이 관리할 경우에 인접한 정점을 참조하기 위해 반복문을 보다 적게 돌릴 수 있다.
가까운 경유점을 찾는 방법의 경우 단순히 인접한 정점의 갯수만큼 반복문을 돌려 구할 수도 있지만
보다 빠르게 구하고자 한다면 경유할 점과 그 점까지의 거리를 우선순위 큐(힙)에 넣어 관리하면 시간복잡도를 O(logn)까지 줄일 수 있다. 큐에 들어있지만 이미 최단거리가 갱신돼버린 케이스의 존재를 감안해도 상당한 성능 향상을 기대할 수 있다.
위 두가지 요소를 적용한 코드는 아래와 같다.
import sys
import heapq
input = sys.stdin.readline
INF = float('inf')
# 1753 최단경로
# 주어진 정점에서 시작하여 각 정점으로의 최단거리를 구하는 문제
# 다익스트라 알고리즘을 활용하여 해결 가능하다
def sol1753():
# 정점의 갯수와 간선의 갯수
v, e = map(int, input().split())
# 시작점
s = int(input())
# 각 정점의 인접 정점과 그 사이의 거리
g = [[] for _ in range(v + 1)]
for _ in range(e):
v1, v2, d = map(int, input().split())
g[v1].append((v2, d))
# 처음에는 모든 정점까지의 거리를 무한으로 초기화(자기 자신과의 거리는 0)
dp = [INF] * (v + 1)
dp[s] = 0
# 경유하는 점의 시작으로 자기 자신을 집어넣음
# 경유할 수 있는 점 중 가장 거리가 짧은 것을 우선적으로 방문하기 위해 우선순위 큐(heapq)를 사용한다
q = [(0, s)]
while q:
distance, vertex = heapq.heappop(q)
# 만약 경유할 정점까지의 거리가 최단거리가 아닐 경우 스킵
if dp[vertex] < distance:
continue
# 시작점부터 경유할 정점까지의 거리 + 경유할 정점의 인접 정점까지의 거리로 시작점부터 인접 정점까지의 거리를 갱신
# 갱신된 경우 해당 정점과 그 정점까지의 거리를 큐에 삽입
for e, d in g[vertex]:
c = dp[vertex] + d
if c < dp[e]:
dp[e] = c
# 우선순위 기준을 거리로 잡기 위해 (거리, 정점번호) 의 형태로 큐에 삽입
heapq.heappush(q, (c, e))
print('\n'.join(map(conv, dp[1:])))
def conv(num):
return 'INF' if num == INF else str(num)
if __name__ == '__main__':
sol1753()백준 온라인저지(Baekjoon Online Judge)의 1753번 문제(https://www.acmicpc.net/problem/1753)에 제출한 코드이다
'코딩테스트 > 알고리즘' 카테고리의 다른 글
| #5 Disjoint Set 알고리즘 (0) | 2021.07.24 |
|---|---|
| #4 최장 증가 부분수열(Longest Increasing Subsequence) 알고리즘 (0) | 2021.07.18 |
| #3 최단거리 알고리즘 - Floyd-Warshall Algorithm (0) | 2021.07.14 |
| #2 최단거리 알고리즘 - Bellman-Ford Algorithm (0) | 2021.07.13 |
| # 0 코딩테스트용 알고리즘 정리 (0) | 2021.07.12 |