이코테-최단 경로 알고리즘

최단 경로 알고리즘에 대해

1. 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘인데, 상황에 맞는 다양하고 효율적인 알고리즘이 이미 정립되어 있다.

2. 보통 그래프로 표현함.

   • 각 지점은 '노드'
   • 지점 간 연결선은 '간선'

     실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다.

3. 학부 수준에서 사용하는 최단 거리 알고리즘에는 3가지가 있음.

   • 다익스트라(Dijkstra) 알고리즘

   • 플로이드 워셜

   • 벨만 포드 알고리즘

     3가지 중 다익스트라와 플로이드 워셜 알고리즘이 코딩 테스트에서 가장 많이 등장하는 유형이다.
     또한 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징이 있다.

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

1. 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘으로, 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정을 반복한다.

2. 음의 간선(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작한다.

   • 현실에서는 음의 간선으로 표현될 일이 없기 때문에 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.

3. 기본적으로 그리디 알고리즘으로 분류된다.

   • 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다.

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

4. 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.

   • 그래서 그리디 알고리즘으로 볼 수 있다.

5. 다익스트라 알고리즘을 구현하는 방법에는 2가지가 있다.

   • 구현하기 쉽지만 느리게 동작하는 코드
   • 구현하기 까다롭지만 빠르게 동작하는 코드

     두 번째 방법을 정확히 이해하고 구현할 수 있어야 한다.

6. 초기 상태에서는 출발 노드를 기준으로 다른 노드로 가는 최단 거리를 무한으로 초기화 한다.

   • 코드로는 999,999,999 또는 987,654,321 등의 값으로 설정할 수 있음.
   • 가장 간단한 방법은 지수표기법을 사용해 1e9로 사용하는 방법도 있다.

     단, 실수 자료형이기 때문에 모든 간선이 정수형으로 표현되는 문제에서는 int(1e9)로 초기화한다.

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

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

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

1. 최악의 경우에도 O(ElogV)를 보장(E: 간선의 개수).
2. Heap 자료구조를 사용한다.
   • 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하기 때문에 더 빠르게 찾을 수 있다.
   • 우선순위 큐(priority queue)를 구현하기 위해 사용하는 자료구조 중 하나
     • 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다.
     • 대부분 언어에서 우선순위 큐 라이브러리를 지원한다(파이썬에서는 PriorityQueue 또는 heapq).
       • heapq가 더 빠르게 동작한다.
     • 정수형 자료형의 변수가 사용된다.

       예: 물건 정보가 있고, 이 물건 정보는 물건의 가치와 물건의 무게로만 구성된다고 가정했을 때, 모든 물건 데이터를 (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있다. 이후 꺼낼 땐 항상 가치가 높은 물건이 먼저 나오게 된다(최대 힙으로 구현한 경우).

     • 보통 큐 라이브러리에 데이터의 묶음을 넣으면 첫번째 원소를 기준으로 우선순위를 정한다.
     • 파이썬에서 제공하는 우선순위 큐 라이브러리는 '최소 힙' 구조를 이용하는데, 다익스트라 알고리즘은 비용이 적은 노드가 우선순위가 높으므로 제공되는 큐 라이브러리를 그대로 사용하는 것이 적합하다.

       또한 일부러 우선순위에 해당하는 값에 음수 부호를 붙여 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음 다시 음수 부호를 붙여 원래의 값으로 돌려놓는, 즉 최소 힙을 최대 힙처럼 사용하는 방식을 사용할 수도 있다. 이런 테크닉도 실제 코테 환경에서 자주 사용함.

     • 우선순위 큐를 구현하기 위해 힙 자료구조 외에 리스트를 이용하여 구현할 수도 있지만 최악의 경우 O(N)의 시간이 소요된다.
     • 중요한 건 우선순위 큐를 적용해도 다익스트라 알고리즘이 동작하는 기본 원리는 같다. 최단 거리를 저장하기 위한 1차원 리스트는 그대로 이용하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다고 보면된다.

플로이드 워셜 알고리즘

1. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용한다.
   • 다익스트라는 한 지점에서 다른 특정 지점 까지의 최단 경로를 구해야 하는 경우
2. 다익스트라처럼 '거쳐가는 노드'를 기준으로 알고리즘을 수행하지만, 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다.
   • 노드의 개수가 N개일 때, 알고리즘상으로 N번의 단계를 수행하고 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다.
   • 따라서 시간복잡도는 O(N^3)이다.
3. 2차원 리스트에 최단 거리 정보를 저장한다.
   • 모든 노드에 대해 다른 모든 노드로 가는 최단 거리 정보를 담아야하기 때문이다.
   • 즉, 2차원 리스트를 처리해야 하니까 N번의 단계에서 매번 O(N^2)의 시간이 소요된다.
4. 그리디 알고리즘이 아니고 DP이다.
   • 노드의 개수가 N이라고 할 때, N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍이라고 볼 수 있다.