최단 경로 알고리즘

Cammie·2022년 7월 4일
다익스트라최단 경로코딩 테스트파이썬플로이드 워셜
0

코딩 테스트

목록 보기
9/10
post-thumbnail

해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️




최단 경로

말 그대로 가장 짧은 경로를 찾는 알고리즘이다.


최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 3가지가 대표적이다. 이 중 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘에 대해 다뤄보도록 하자.


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

다익스트라 최단 경로 알고리즘은 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이 다익스트라 최단 경로 알고리즘은 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘으로 분류된다.


알고리즘의 원리는 다음과 같다.

  1. 출발 노드를 설정

  2. 최단 거리 테이블을 초기화

    초기 상태에서는 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화 한다.

    • 999,999,999 (약 10억)으로 설정해주면 된다. => int(1e9)

  3. 방문하지 않은 노드 중, 최단 거리가 가장 짧은 노드를 선택

  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여, 최단 거리 테이블을 갱신

  5. 3과 4번을 반복

항상 1차원의 리스트에 '각 노드에 대한 현재까지의 최단 거리' 정보를 저장하며 리스트를 계속 갱신한다. 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면, 이를 갱신하는 것이다.


이미지 출처: https://haningya.tistory.com/116



다익스트라 알고리즘은 구현하기 쉽지만, 느리게 동작하는 코드와 구현하기 조금 까다롭지만, 빠르게 동작하는 코드 2가지로 구현할 수 있다.

그러나 코딩 테스트를 준비한다면, 조금 까다롭지만 빠르게 동작하는 코드를 정확하고 제대로 구현할 수 있을 때까지 연습해야 한다.



방법 1: 간단한 다익스트라 알고리즘

간단한 다익스트라 알고리즘은 O(V2)의 시간 복잡도를 가지며, 처음 고안된 다익스트라 알고리즘이다. 이때 V는 노드의 개수를 의미한다. 


import sys
# input()을 더 빠르게 동작하는 sys.stdin.readline()으로 치환
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[i] == INF:
        pritn("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
# 출력 예시
0
2
3
1
2
4

위 알고리즘은 총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색을 하고, 현재 노드와 연결된 노드를 매번 일일이 확인해야 되므로, 시간복잡도가 O(V2)인 것이다.

따라서, 노드의 개수가 10,000개를 넘어가면 보다 효율적으로 개선된 다익스트라 알고리즘을 이용해야 한다.



방법 2: 개선된 다익스트라 알고리즘

이 구현방법을 사용하면 다익스트라 최단 경로 문제가 최악의 경우에도 시간 복잡도 O(ElogV)를 보장할 수 있다. 이때 V는 노드의 개수이고, E는 간선의 개수를 의미한다.

개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다. 이렇게 함으로 선형 시간이 아닌 로그 시간이 걸려, 이전에 비해 매우 빠른 속도를 지니게 된다.


힙 (Heap)

우선순위 큐(Priority Queue)를 구현하기 위하여 사용하는 자료구조 중 하나이다.

큐는 가장 먼저 삽입된 데이터를 가장 먼저 삭제하는 선입선출(First In First Out) 구조를 가졌었다.

이처럼 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.


자료구조추출되는 데이터
스택(Stack)가장 나중에 삽입된 데이터
큐(Queue)가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)가장 우선순위가 높은 데이터

따라서 가치가 높은 데이터부터 확인해야 하는 경우, 우선순위 큐 자료구조를 이용하면 효과적이다. 이러한 우선순위 큐는 라이브러리로 지원을 하므로, 직접 구현하는 코드를 공부하지 않아도 된다.

파이썬에서는 heapq를 사용하여 우선순위 큐 기능을 이용하도록 하자.

또한, 우선순위 값을 표현할 때에는 일반적으로 정수형 자료형을 사용한다는 점을 알아두자.


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

최단 거리를 저장하기 위해 1차원 리스트를 사용하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐를 추가로 이용할 것이다.


++ 최소 힙을 최대 힙처럼 사용하기 위해서는 데이터를 넣을 때 우선순위 값에 음수를 붙인 후, 우선순위 큐에서 꺼낸 후 다시 음수를 붙여 원래의 값으로 돌리는 식으로 사용할 수 있다.


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)]
# 최단 거리 테이블을 모두 무한으로 초기화
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:
        pritn("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
# 출력 예시
0
2
3
1
2
4


플로이드 워셜 알고리즘

다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우에 사용했던 알고리즘이었던 반면, 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다.


이 둘의 차이를 먼저 알아본 후, 플로이드 워셜에 대해 더 자세히 살펴보자.


다익스트라 알고리즘 VS 플로이드 워셜 알고리즘

  • 다익스트라 알고리즘

단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택하여, 해당 노드를 거쳐 가는 경로를 확인하며 최단 거리 테이블을 갱신하는 방식으로 동작한다.

최단 거리 테이블로 1차원 리스트를 이용한다.

그리디 알고리즘을 바탕으로 한다.


  • 플로이드 워셜 알고리즘

단계마다 현재 노드를 거쳐가는 경로를 기준으로 알고리즘을 수행한다.

노드의 개수가 N개일 때, 알고리즘 상 N번의 단계를 수행하며, 이때 각 단계는 O(N2)의 연산을 한다. 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N3)이다.

최단 거리 테이블로 2차원 리스트를 이용한다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다.

다이나믹 프로그래밍을 바탕으로 한다.


다익스트라플로이드 워셜
1차원 리스트를 이용2차원 리스트를 이용
그리디 알고리즘 바탕다이나믹 프로그래밍 바탕


플로이드 워셜 알고리즘

현재의 노드를 제외하고 서로 다른 노드 쌍 (A, B)를 선택한다.
이후 A → 현재의 노드 → B 로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다.
즉, 노드의 개수가 N이라고 할 때, N-1P2개의 쌍을 매 단계마다 반복해서 확인하는 것이다.

이를 점화식으로 표현하면 다음과 같다.

Dab=min(Dab, Dak+Dkb)D_{ab} = min(D_{ab},\,D_{ak}+D_{kb})

이전까지의 A에서 B로 가는 최소비용과 현재 노드 K를 거쳐가는 비용을 비교하여 작은 값을 갱신한다는 의미이다.


이를 바탕으로 한 소스코드는 다음과 같다.


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())
    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()

# 입력 예시
4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
# 출력 예시
0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0



profile
Cammie
이전 포스트

다이나믹 프로그래밍(Dynamic Programming) 알고리즘

다음 포스트

그래프 이론 알고리즘

0개의 댓글