최단 경로

최단 경로란?

특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘

 

다양한 문제 상황

1. 한 지점에서 다른 한 지점까지의 최단 경로
2. 한 지점에서 다른 모든 지점까지의 최단 경로 (다익스트라 알고리즘)
3. 모든 지점에서 다른 모든 지점까지의 최단 경로 (플로이드 워셜 알고리즘)

각각 사례에 맞는 알고리즘을 알고 잇다면 문제에 더 쉽게 접근 가능하다.

 

각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 노드를 그래프에서 간선으로 표현한다.

 

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

그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

 

다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작하고, 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.

 

다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.

매 상황에서 가장 비요잉 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.

 

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

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

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신하는 특징이 있다. (최단 거리 테이블)

 

매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인하여, 더 짧은 경로가 있는지 확인하며 갱신해 나간다.

따라서 '방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 선택'하는 4번 과정 통해 그리디 알고리즘임을 확인할 수 있다.

 

위에서 선택된 노드는 '최단 거리'가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다.

 

이는 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것이므로, 마지막 노드에 대해서는 굳이 다른 노드로 가는 경우를 확인할 필요가 없다. 이미 이전 노드들의 최단 거리들이 확정되어 있기 때문이다.

 

 

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

간단한 다익스트라 알고리즘은 O(V^2)의 시간 복잡도를 갖는다.

 

V는 노드의 개수를 의미하고, 해당 알고리즘은 직관적이고 이해하기가 쉽다.

 

각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언하고, 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택' 하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)한다.

 

 

다익스트라 알고리즘에서 입력되는 데이터의 수가 많기 때문에, 파이썬 내장 함수인 input()을 더 빠르게 동작하는 sys.stdin.readline()을 치환하여 사용하는 방법을 적용하였다.

 

 

간단한 다익스트라 알고리즘 코드

간단한 다익스트라 알고리즘의 시간 복잡도

V는 노드의 개수이다.

총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문에 시간 복잡도는 O(V^2)이다.

 

최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 위 방식으로 해결가능하다. 

하지만 노드의 개수가 10,000개 이상이라면 위 방식으로는 해결이 불가능하다.

노드의 개수와 간선의 개수가 많을 때는 '개선된 다익스트라 알고리즘'을 이용해야 한다.

 

 

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

위의 방식과는 다르게, 개선된 다익스트라 알고리즘은 최악의 경우에도 시간 복잡도 O(ElogV)를 보장하여 해결할 수 있다. V는 노드의 개수, E는 간선의 개수를 의미한다.

 

간단한 다익스트라 알고리즘은 '최단 거리가 가장 짧은 노드'를 찾기 위해서, 매번 최단 거리 테이블을 선형적으로 탐색했다. 이 과정에서만 O(V)의 시간이 걸린다.

 

개선된 다익스트라 알고리즘은 힙(Heap) 자료구조를 사용한다.

힙 자료구조를 사용하면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로, 출발 노드로부터 가장 거리가 짧은 노드를 빠르게 찾을 수 있다. 이 과정에서 선형 시간이 아닌 로그시간이 걸리기 때문에 더욱 효율적이다.

 

 

힙(heap)

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

 

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

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

대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정한다.

따라서 데이터가 (가치, 물건)으로 구성된다면, '가치'값이 우선순위 값이 되는 것이다.

 

우선순위 큐를 구현할 때 내부적으로 최소 힙 혹은 최대 힙을 이용한다.

 

최소 힙	값이 낮은 데이터가 먼저 삭제
최대 힙	값이 큰 데이터가 먼저 삭제

 

"파이썬 라이브러리에서는 기본적으로 최소 힙 구조를 이용하는데, 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로 최소 힙 구조를 기반으로 하는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합하다.

 

최소 힙을 최대 힙처럼 사용하기 위해 일부러 우선순위에 해당하는 값에 음수 부호를 붙였다가, 나중에 우선순위 큐에서 꺼낸 다음 다시 음수 부호를 붙이면 원래의 값을 돌리는 방식을 사용한다."

 

 

단순히 우선순위 큐를 이용해서 시작 노드로부터 '거리'가 짧은 노드 순서대로 큐에서 나올 수 있도록 다익스트라 알고리즘을 사용하면 된다.

 

우선순위 큐를 적용하여도 다익스트라 알고리즘의 동작 기본 원리는 동일하다.

 

최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블)는 아까와 같이 그대로 이용하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다.

 

앞의 간단한 다익스트라 알고리즘의 get_smallest_node()라는 함수를 작성할 필요가 없다.

'최단 거리가 가장 짧은 노드'를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체할 수 있기 때문이다.

 

 

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

개선된 다익스트라 알고리즘의 시간 복잡도

간단한 다익스트라 알고리즘에 비해 개선된 다익스트라 알고리즘은 시간 복잡도가 O(ElogV)로 훨씬 빠르다.

 

위 코드의 31, 32번째 줄을 보면, 한 번 처리된 노드를 더 이상 처리하지 않는다.

 

즉, 큐에서 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V 이상의 횟수로는 반복되지 않는다.

 

또한 V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인한다.

 

따라서 '현재 우선순위 큐에서 꺼낸 노드와 연결된 노드들을 확인'하는 총 횟수는 최대 간선의 개수(E)만큼 연산이 수행된다.

 

 

 

플로이드 워셜 알고리즘

다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우' 사용할 수 있는 최단 경로 알고리즘이다.

 

플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다.

 

다익스트라 알고리즘은 단계마다 최단 거리를 갖는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다.

 

플로이드 워셜 알고리즘 또한 단게마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다.

 

하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 것이 차이점이다.

 

노드의 개수가 N개일 때, 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 

 

그러므로 플로이드 워셜 알고리즘의 총시간 복잡도는 O(N^3)이다.

 

다익스트라 알고리즘에서는 출발노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해 1차원 리스트를 이용했지만, 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 다르게 2차원 리스트에 '최단 거리' 정보를 저장한다.

모든 노드에 대하여 다른 모든 노드로가는 최단 거리 정보를 담아야 하기 때문이다.

 

최단 거리 저장

다익스트라 알고리즘	플로이드 워셜 알고리즘
1차원 리스트(1개 노드 -> 모든 노드)	2차원 리스트 (모든 노드 -> 모든 노드)

 

 

2차원 리스트를 처리해야 하기 때문에 N번의 단계에서 매번 O(N^2)의 시간이 소요된다.

 

또한 다익스트라 알고리즘은 그리디 알고리즘인데, 플로이드 워셜 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다.

 

노드의 개수가 N개라면, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문이다

위 점화식을 해석해보면, 'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교하여 더 작은 값으로 갱신한다는 의미다.

즉, '바로 이동하는 거리'가 '특정 노드를 거쳐 이동하는 거리'보다 더 많은 비용을 가진다면, 더 짧은 거리로 갱신하겠다는 의미다.

 

 

플로이드 워셜 알고리즘 

 

 

 

미래 도시

문제 : 교재 259p 참고

 

나의 코드

본인은 우선순위 큐를 사용해서 다익스트라 알고리즘을 통해 문제를 해결하였다.

시작점을 1로 세팅한 후, 1에서 k까지의 최단 거리를 d1에 저장하였고

다시 시작점을 k로 세팅한 후, k에서 x까지의 최단 거리를 d2에 저장한 후,

두 거리의 합을 구한 뒤, 해당 값이 무한 값인지를 판별한 후, 출력하였다.

 

 

해설을 참고한 코드

해설에서는 플로이드 워셜 알고리즘을 사용하였다.

 

N의 범위가 100이하로 매우 한정적이여서, 플로이드 워셜 알고리즘을 이용해도 빠르게 풀 수 있기 때문에, 구현이 간단한 플로이드 워셜 알고리즘을 사용하는 것이 유리하다.

 

플로이드 워셜 알고리즘의 복잡도가 높다고 생각해서 최대한 안쓰는 쪽으로 생각을 했는데, 생각해보니 다루는 범위가 매우 적어서 크게 상관이 없었던거 같다. 문제를 확인할 때 입력 범위들도 확실히 확인하는 습관을 들여야겠다.

 

 

 

전보

문제 : 교재 264p 참고

 

나의 코드

본인은 입력받은 값들을 토대로, 플로이드 워셜 알고리즘을 사용하여 각각의 최단 거리를 찾은 후, 출발 도시로부터 다른 모든 도시와 연결되어 있는지의 여부를 확인한 후, 연결되어있다면, count값을 증가시키고, 걸리는 시간들 중의 최댓값을 구해서, count값과 최장 시간값을 출력하였다.

 

 

해설을 참고한 코드

해설은 본인과 다르게 우선순위 큐를 사용하여 다익스트라 알고리즘으로 문제를 해결하였다.

 

위의 문제와 같은 이유에서이다.

 

입력값의 범위가 1 <= N <= 30,000 , 1 <= M <= 200,000, 1<= C <= N 으로 충분히 크기 때문에, 우선순위 큐를 이용하여 다익스트라 알고리즘을 작성하는 것이 좋다.

 

 

 

느낀점

생각보다 엄청 어렵지는 않았다. 책에 있는 예시 그래프들을 보고 차근차근 순차적으로 접근하고 코드와 비교해보니, 이해가 잘 된거 같다. 우선순위 큐의 역할도 따로 구현할 필요없이 적절히 사용만 할 줄 알면 되기 때문에, 크게 어려운 느낌은 들지 못했다. (물론 고난이도 문제를 접하지 않은 기초단계이기 때문이라고 생각한다.)

실전문제1, 2번도 풀긴 했지만, 입력값 범위를 제대로 확인하지 않아 필자가 의도한 알고리즘을 사용하지 않았다.

문제를 푸는 것 뿐만 아니라, 문제들의 조건들도 중요한데 말이다.

입력값 범위, 시간 복잡도 등등.... 잊지 말고 신경쓰자