최단 경로 알고리즘 (이것이 취업을 위한 코딩 테스트다)

March 08, 2022

이것이 취업을 위한 코딩 테스트다를 정리한 글입니다.

최단 경로 문제

가장 짧은 경로를 찾는 알고리즘이다. 각 지점은 그래프에서 노드로 표현이 되고 지점 간 연결된 도로는 그래프에서 간선으로 표현된다.

최단 경로 문제는 다앙한 문제 상황이 있다.

한 지점에서 다른 한 지점까지의 최단 경로
한 지점에서 다른 모든 지점까지의 최단 경로
모든 지점에서 다른 모든 지점까지의 최단 경로

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

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 대 정상적으로 동작한다.

다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류되며 매 상황에서 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복한다.

다익스트라 최단 경로 알고리즘의 동작 과정

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

다익스단 경로 알고리즘 예제 코드

import sys
input = sys.stdin.readline
# > 테이블 초기화 시
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
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[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

다익스트라 알고리즘 성능 분석

총 $O(V)$번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 한다. 현재 노드와 연결된 노드를 매번 확인해야되므로 시간 복잡도는 $O(V^2)$이다.

문제에서 노드의 개수가 5,000개 이하라면 다익스트라 알고리즘을 사용할 수 있지만, 10,000개를 넘어가는 문제에서는 해결하기 힘들다. 이를 해결할 수 있는 개선된 다익스트라 알고리즘을 알아보자.

개선된 다익스트라 알고리즘

개선된 다익스트라 알고리즘에서는 heap자료구조를 사용한다. 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리하기 때문에 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.

Heap

heap자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나이다. 우선순위 큐는 우선순위가 가장 높은 데이터를 먼저 삭제하는 특징을 가지고 있다. 파이썬에는 우선 순위 큐를 사용할 수 있는 PriorityQueue클래스와 heapq모듈이 있다. 두 가지의 라이브러리의 차이를 설명한 내용은 아래에서 확인할 수 있다.

👉PriorityQueue와 heapq

heap자료구조에는 최소 힙과 최대 힙이 있다. 최소 힙은 가장 작은 데이터가 우선으로 삭제되며 최대 힙은 가장 큰 데이터가 먼저 삭제 된다. 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선으로 하여 방문하기 때문에 최소 힙 구조의 우선순위 큐를 사용하면 적합하다.

최소 힙

import heapq

# 최소 힙

def heapsort(iterable):
    h = []
    result = []

    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

최대 힙

import heapq

# 최소 힙

def heapsort(iterable):
    h = []
    result = []

    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

개선된 다익스트라 알고리즘의 동작

다익스트라 알고리즘과 기본 원리는 동일하지만, 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가로 사용하는 부분이 다르다.

초기 상태

이것이 취업을 위한 코딩테스트다

출발 노드를 1로 설정하고 출발 노드를 제외한 모든 노드의 거리를 무한으로 초기화 해준다. 우선 순위 큐에 튜플 형식으로 (거리, 노드)를 넣게 되고 (0, 1)을 추가하게 된다. 현재 우선순위 큐에는 하나의 튜플이 존재한다.

Step1

이것이 취업을 위한 코딩테스트다

우선순위 큐에서 원소를 꺼내 방문 처리를 해준다. 꺼낸 원소는 (0, 1)이며, 노드 1과 이웃인 노드는 4, 2, 3이 존재한다. 각 노드들의 거리와 노드 번호를 우선순위 큐에 넣어주며 각 노드 까지의 거리를 갱신해 준다.

Step2

이것이 취업을 위한 코딩테스트다

step1의 우선순위 큐에서 원소를 꺼내 방문 처리를 한다. 꺼내진 원소는 (1, 4)가 되고, 인접한 원소들을 확인한다. 인접한 원소는 3과 5이며, 4번 노드를 거쳐가는 경우 4번 노드의 거리 1과 4번에서 각 노드까지의 거리를 더한다. 더해진 값들과 이전 단계의 거리를 비교해 작은 값으로 갱신하게 된다. 확인한 노드들을 우선순위 큐에 넣어주게 되고 거리가 작은 튜플이 우선순위를 가지게 된다. 이후의 단계들은 앞서 봤던 동작과 동일하다.

개선된 최단 경로 알고리즘

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
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 distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

입력

출력

개선된 다익스트라 알고리즘 성능 분석

노드를 하나씩 꺼내서 검사하는 반복문은 노드의 개수 V이상으로는 처리되지 않는다. 한번 방문했던 노드는 확인하지 않기 때문이다. 그러므로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선 개수 E만큼 연산이 수행될 수 있다. 따라서 E개의 원소를 우선순위 큐에 넣었다가 빼는 연산과 유사하며, 시간복잡도는 $O(ElogV)$로 볼 수 있다.

플로이드 워셜 알고리즘

모든 노드에서 다른 노드까지의 최단 경로를 모두 계산하는 알고리즘이다. 단계별로 거쳐가는 노드를 기준으로 동작한다. 2차원 테이블에 최단 거리 정보를 저장하며, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.

각 단계마다 특정 노드 k를 거쳐 가는 경우를 확인한다. a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다. 점화식은 아래와 같다

$$ D_{ab} = min(D_{ab}, D_{ak}+D_{kb}) $$

초기 상태

이것이 취업을 위한 코딩테스트다

단순하게 각 노드를 기준으로 인접 노드를 2차원 테이블에 저장하게 된다. 행은 출발노드, 열은 도착 노드를 의미한다.

Step1

이것이 취업을 위한 코딩테스트다

하늘색 부분은 갱신되는 값들이다. 1에서 갈 수 있는 부분에 대해 최소 비용을 계산한 것이다. 1번을 거쳐갈 경우를 확인해서 최단 거리를 테이블에 갱신한다. 각각의 노드를 방문하며 테이블 값들을 갱신해 나간다.

플로이드 워셜 알고리즘 코드

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):
    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):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == 1e9:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()