최단경로
가장 빠르게 도달하는 방법
최단 경로 (Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다.
최단 경로 문제는 보통 그래프를 이용해 표현한다. 각 지점은 그래프에서 ‘노드'로 표현되고, 지점간 연결된 도로는 그래프에서 ‘간선'으로 표현된다.
코딩 테스트에서 가장 많이 등장하는 유형의 최단경로 알고리즘은 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘 이다.
다익스트라 최단 경로 알고리즘
다익스트라(Dijkstra) 최단 경로 알고리즘은 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
‘음의 간선'이 없을 때 정상적으로 동작한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다.
현실 세계의 길은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되기도 한다.
다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 ‘가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다.
👉🏻 원리
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3 과 4번을 반복한다.
다익스트라 알고리즘은 최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.
다익스트라 알고리즘의 동작 원리를 보면
1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제라고 할때
예시에서 출발 노드를 1이라고 하고 1번 노드에서 다른 모든 노드로의 최단 거리를 계산해볼 것이다.
초기 상태에서는 다른 모든 노드로 가는 최단 거리를 ‘무한'으로 초기화한다. 무한으로 처리하는 여러 방법이 있으며 가장 간단한 방법은 지수표기법을 사용하는 것이다. int(1e9)로 사용한다.
step 0
먼저 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발 노드가 선택된다.
step 1
이제 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 즉, 1번 노드와 연결된 모든 간선을 하나씩 확인하면 된다. 현재 1번 노드까지 오는 비용은 0이므로, 1번 노드를 거쳐서 2번, 3번, 4번 노드로 가는 최소 비용은 차례대로 2(0 + 2), 5(0 + 5), 1(0 + 1)이다. 현재 2번, 3번, 4번 노드로 가는 비용이 ‘무한'으로 설정되어 있는데, 세 노드에 대하여 더 짧은 경로를 찾았으므로 각각 새로운 값으로 갱신한다.
step 2
모든 단계에서도 마찬가지로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해야 한다.
따라서 [step 2]에서는 4번 노드가 선택된다. 4번 노드에서 갈 수 있는 노드는 3번과 5번이다. 이때 4번 노드까지의 최단 거리는 1이므로 4번 노드를 거쳐서 3번과 5번 노드로 가는 최소 비용은 차례대로 4(1 + 3), 2(1 + 1)이다. 이 두값은 기존의 리스트에 담겨 있던 값보다 작으므로 다음처럼 리스트가 갱신된다.
step 3
[step 3]에서는 2번 노드가 선택된다. 2번과 5번 노드까지의 최단거리가 2로 값이 같은데, 이럴 때는 일반적으로 번호가 작은 노드를 선택한다. 그리고 2번 노드를 거쳐서 도달할 수 있는 노드 중에서 거리가 더 짧은 경우가 있는지 확인한다. 이번 단계에서 2번 노드를 거쳐서 가는 경우, 현재의 최단 거리를 더 짧게 갱신할 수 있는 방법은 없다.
step 4
이번에는 5번 노드가 선택된다. 5번 노드를 거쳐 3번과 6번 노드로 갈 수 있다. 현재 5번 노드까지 가는 최단 거리가 2이므로 5번 노드에서 3번 노드로 가는 거리인 1을 더한 3이 기존 값인 4보다 작기 때문에 새로운 값 3으로 갱신된다. 또한 6번 노드로 가는 거리도 마찬가지로 4로 갱신된다.
step 5
이어서 3번 노드를 선택한 뒤에 동일한 과정을 반복한다.
step 6
6번 노드를 선택한 후 같은 과정을 반복한다. 지금까지의 최종 최단 거리 테이블은 다음과 같다.
최단 거리 테이블이 의미하는 바는 1번 노드로부터 출발했을 때 2번, 3번, 4번, 5번, 6번 노드까지 가기 위한 최단 경로가 각각 2, 3, 1, 2, 4라는 의미다.
다익스트라 최단 경로 알고리즘에서 “방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택”하는 과정을 반복하는데, 이렇게 선택된 노드는 ‘최단 거리'가 완전히 선택된 노드이므로 더이상 알고리즘을 반복해도 최단거리가 줄어들지 않는다. 앞서 [step 6]까지의 모든 경우를 확인해보면, 실제로 한 번 선택된 노드는 최단 거리가 감소하지 않는다.
다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 볼 수 있다.
그렇기 때문에 사실 마지막 노드에 대해서는 해당 노드를 거쳐 다른 노드로 가는 경우를 확인할 필요가 없다.
힙 설명
힙 자료구조는 우선순위 큐(Priority Queue)를 구현 하기 위하여 사용하는 자료구조 중 하나다.
스택(Stack)은 가장 나중에 삽입된 데이터를 가장 먼저 삭제하고, 큐(Queue)는 가장 먼저 삽입된 데이터를 가장 먼저 삭제한다.
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.
우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예시로 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우를 가정할 때 우선순위 큐 자료구조를 이용하면 효과적이다.
파이썬 에서는 우선순위 큐가 필요할 때 PriorityQueue 혹은 heapq를 사용할 수 있는데, 이 두 라이브러리는 모두 우선순위 큐 기능을 지원한다. 일반적으로 heapq가 더 빠르게 동작하기 떄문에 수행 시간이 제한된 상황에서는 heapq가 권장된다.
우선순위 값을 표현할 때는 읿잔적으로 정수형 자료형의 변수가 사용된다. 예를 들어 물건 정보가 있고, 이 물건 정보는 물건의 가치와 물건의 무게로만 구성된다고 가정할 때, 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있다. 이후에 우선순위 큐에서 물건을 꺼내게 되면, 항상 가치가 높은 물건이 먼저 나오게 된다. 대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리에 데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정한다. 따라서 데이터가 (가치, 물건)으로 구성된다면 ‘가치'값이 우선순위 값이 되는 것이다.
우선순위 큐를 구현할 때는 내부적으로 최소 힙(Min Hep) 혹은 최대 힙(Max Heap)을 이용한다.
- 최소 힙을 이용하는 경우 ‘값이 낮은 데이터가 먼저 삭제'되며,
- 최대 힙을 이용하는 경우 ‘값이 큰 데이터가 먼저 삭제' 된다.
다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로 최소 힙 구조를 기반으로 하는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합하다.
또한 최소 힙을 최대 힙처럼 사용하기 위해서 일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호(-)를 붙여서 원래의 값으로 돌리는 방식을 사용할 수 있다.
우선순위 큐를 구현할 때는 보통 힙 자료구조를 이용한다고 했는데, 사실 우선순위 큐를 구현하는 방법은 다양하다.단순히 리스트를 이용해서 구현할 수도 있다. 데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도를 비교하면 아래와 같다.
리스트를 이용해서 우선순위 큐의 기능을 구현하기 위해서는 삭제할 때마다 모든 원소를 확인해서 우선 순위가 가장 높은 것을 찾아야 하므로 최악의 경우 O(N)의 시간이 소요된다.
데이터의 개수가 N개일 때 힙 자료구조에서의 시간 복잡도는
삽입할 때는 O(logN)의 연산을 N번 반복하므로 O(NlogN)이고 삭제할 때에도 O(logN)의 연산을 N번 반복하므로 O(NlogN)이다.
최소 힙을 이용하는 경우 힙에서 원소를 꺼내면 ‘가장 값이 작은 원소'가 추출되는 특징이 있으며, 파이썬의 우선순위 큐 라이브러리는 최소 힙에 기반한다.
우선 순위 큐를 적용하여도 다익스트라 알고리즘이 동작하는 기본 원리는 동일하다.
최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블)는 아까와 같이 그대로 이용하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다.
플로이드 워셜 알고리즘
다익스트라 알고리즘은 ‘한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다. **플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)**은 ‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우’에 사용할 수 있는 알고리즘이다.
다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘 또한 단계마다 ‘거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다.
노드의 개수가 N개 일때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 ‘현재 노드를 거쳐 가는’ 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 총시간 복잡도는 O(N^3)이다.
다익스트라 알고리즘에서는 출발 노드 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용했다. 반면에 플로이드 워셜 알고리즘은 다익스트라 알고리즘과는 다르게 2차원 리스트에 ‘최단 거리' 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로가는 최단 거리 정보를 담아야 하기 때문이다. 다시 말해 2차원 리스트를 처리해야 하므로 N번의 단계에서 매번 O(N^2)의 시간이 소요된다.
또한 다익스트라 알고리즘은 그리디 알고리즘인데 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 이라는 특징이 있다. 노드의 개수가 N이라고 할 때, N번 만큼의 단계를 반복하며 ‘점화식에 맞게' 2차원 리스트를 갱신하기 떄문에 다이나믹 프로그래밍으로 볼 수 있다.
각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다. 예를 들어 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 겨우를 고려하면 된다. 정확히는 A → 1번 노드 → B로 가는 비용을 확인한 후에 최단 거리를 갱신한다. 이를테면 현재 최단 거리 테이블에 A번 노드에서 B번 노드로 이동하는 비용이 3으로 기록되어 있을 때, A번 노드에서 1번 노드를 거쳐 B번 노드로 이동하는 비용이 2라는 것이 밝혀지면, A번 노드에서 B번 노드로 이동하는 비용을 2로 갱신하는 것이다.
출처 : 이것이 취업을 위한 코딩 테스트다 (https://g.co/kgs/cemQ62)