[#알고리즘/최단 경로]

🤷‍♀️ 최단 경로 알고리즘

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 이는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드(node)'로 표현되고, 연결된 도로는 그래프에서 '간선(edge)'으로 표현된다. 더불어 최단 경로 알고리즘에선 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용된다는 특징이 있다. 이번에 배울 최단 경로 알고리즘은 다익스트라 최단 경로와 플로이드 워셜 알고리즘이다.

---

🔉 다익스트라 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이는 '음의 간선(0보다 작은 값을 가지는 간선)'이 없을 때 정상적으로 동작한다.

다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 반복하기 때문이다. 알고리즘의 원리는 대략 아래와 같다.

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
   (처음에는 출발 노드가 선택됨.)
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 3과 4번 과정 반복

초기 상태에서는 출발노드에서 출발노드로의 거리는 0이며, 다른 모든 노드로 가는 최단 거리는 '무한'으로 초기화한다. 나는 '무한'을 파이썬으로 int(1e9), 즉 10억으로 초기화할 것이다.

매번 현재 노드, 즉 3번에서 선택된 노드에서 각 노드로 가는 최단 거리 정보를 1차원 리스트에 저장하며 리스트를 계속 갱신한다. 이때 이미 선택된 노드 or 노드로 가는 정보가 없는 경우 or 최단 거리가 아닐 경우에는 갱신하지 않는다. 만약, 두 개 이상의 노드까지의 최단 거리 값이 같을 경우 번호가 작은 노드를 선택한다.

최종적으로 최단 거리 테이블이 의미하는 바는 출발 노드로부터 각 노드까지 가기 위한 최단 경로 값이다.

힙(Heap)을 사용한 다익스트라 알고리즘 구현

👨‍🏫 힙이란 ?

힙이란, 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 우선순위 큐(Priority Queue)를 구현하기 위한 자료구조 중 하나이다. 대부분의 프로그래밍 언어에서 우선순위 큐 라이브러리를 지원하므로 코딩 테스트 환경에서 직접 구현할 일은 없다. 파이썬에서는 우선순위 큐가 필요하면 heapq를 사용하는 것을 권장한다.

우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용된다. 예를 들어 물건 정보가 물건의 가치와 무게로 구성되있다면, 물건 데이터를 (가치, 물건)으로 묶어 우선순위 큐 자료구조에 넣을 수 있다. 이후에 여기서 물건을 꺼내게 되면 항상 가치가 높은 물건이 먼저 나온다. 대부분 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소(ex) 가치)를 기준으로 우선순위를 설정한다.

👨‍💻 우선순위 큐를 이용한 다익스트라 알고리즘 구현

우선순위 큐를 구현할 때는 최소 힙 혹은 최대 힙을 이용한다. 최소 힙을 이용하는 경우 '값이 낮은 데이터가 먼저 삭제'되며, 최대 힙을 이용하는 경우 '값이 큰 데이터가 먼저 삭제'된다. 파이썬에서 다익스트라 알고리즘은 비용이 적은 노드를 우선 방문하므로 최소 힙 구조를 기반으로 하는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합하다.

즉, 정리하자면 최소 힙의 경우 '가장 값이 작은 원소'가 추출되고, 파이썬의 우선순위 큐 라이브러리는 이러한 최소 힙에 기반한다. 이를 이용해 시작 노드로부터 거리가 짧은 노드 순대로 큐에서 나오도록 다익스트라 알고리즘을 작성하자.

최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블)와 현재 가장 가까운 노드를 저장하기 위한 목적으로만 쓰일 우선순위 큐를 사용한다.

(거리, 노드)의 정보를 튜플 형식으로 우선순위 큐에 넣어 거리 순으로 정렬되게 한다. 파이썬의 heapq 라이브러리는 원소로 튜플을 입력받으면 튜플의 첫번째 원소를 기준으로 우선순위 큐를 구성한다.

거리가 짧은 원소가 우선순위 큐의 최상위에 위치하기 때문에 우리는 거리가 가장 짧은 노드를 선택하기 위해 우선순위 큐에서 노드를 그냥 꺼내면 된다. 해당 노드를 이미 처리한 적이 있다면 무시하고, 아직 처리하지 않은 노드에 대해서만 처리한다.

즉, '최단 거리가 가장 짧은 노드'를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 진행한다. 힙을 사용한 다익스트라 알고리즘의 동작은 아래와 같다.

1. 출발 노드를 제외한 모든 노드의 거리를 무한으로 설정
2. 우선순위 큐에 출발 노드 정보 삽입. (거리, 노드)
3. 우선순위 큐에서 원소 꺼내기
4. 꺼낸 원소 노드를 기준으로 갈 수 있는 노드까지의 최단 거리 정보 갱신 (최단 거리 테이블 갱신)
5. 더 짧은 경로를 찾은 노드 정보들은 다시 우선순위 큐에 삽입.
6. 3번, 4번, 5번 과정 반복

최단 거리 탐색에서 최단 거리 테이블과 우선순위 큐가 어떻게 변하는지의 과정은 여기를 참고하자.

💻 Code

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수, 간선의 개수 
n, m = map(int, input().split())
# 출발 노드 번호 입력받기
start = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
# 모든 리스트는 (노드 개수 + 1)로 할당하여, 노드의 번호를 인덱스로 하여 바로 리스트에 접근하도록 함.
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)
    
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) :
    # 도달할 수 없는 경우, INFINITY이라고 출력
    if dijkstra[i] == INF :
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else :
        print(distance[i])

---

🔊 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용한다. 플로이드 워셜 또한 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 다익스트라와 달리 매번 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾을 필요가 없다.

다익스트라 알고리즘은 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해 1차원 리스트를 이용했다. 반면에 플로이드 워셜 알고리즘은 2차원 리스트에 '최단 거리' 정보를 저장한다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다.

또한 그리디 알고리즘인 다익스트라 알고리즘에 비해 플로이드 워셜 알고리즘은 노드의 개수가 N이라 할때, N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하므로 다이나믹 프로그래밍으로 볼 수 있다.

각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다. 예를 들어 1번 노드에 대해 확인한다고 해보자. A 노드에서 B 노드로 가는 비용이 3일 때, A 노드 -> 1번 노드 -> B 노드로 가는 비용이 2이면 A 노드에서 B 노드로 가는 비용을 2로 갱신한다.

즉, 현재 확인하고 있는 노드를 제외한 N - 1개의 노드 중 서로 다른 노드 (A, B) 쌍을 선택하여 확인 중인 노드를 거쳐가는 비용을 확인한 뒤에 최단 거리이면 값을 갱신한다. 예를 들어 노드 개수가 4개이면 step 4까지 진행되고, 각 step마다 3P2개(4-1개의 노드 중 가능한 모든 1쌍)의 경우를 따져 최단 거리 테이블을 갱신한다. 점화식은 아래와 같다.

위 점화식의 의미는 A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신하겠다는 의미이다.

플로이드 워셜 알고리즘을 이용해 최단 거리 비용을 구하는 과정은 여기를 참고하자.

💻 Code

import sys

input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수 및 간선의 개수
n = int(input())
m = int(input())

# 2차원 리스트를 만들고, 모든 값을 무한으로 초기화
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())
    # 입력받은 비용이 더 작다면 입력값으로 설정
    if graph[a][b] > c :
        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) :
         # 도달할 수 없는 경우, INF 출력
         if graph[a][b] == INF :
             print("0", end=" ")
         # 도달할 수 있는 경우 거리 출력
         else :
             print(graph[a][b], end=" ")         
     print()

Reference
『이것이 코딩 테스트다 with 파이썬』, 나동빈 지음