저희는 이번 스터디에서 다익스트라(Dijkstra) 알고리즘에 대해서 공부했습니다.
일단, 최단 경로(Shortest Path) 문제에 대해서 설명하자면 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제입니다.
그래프의 최단 경로를 구하는 다양한 알고리즘들이 존재합니다.
- 간선의 가중치가 모두 같은 그래프일 경우 -
BFS(너비 우선 탐색) - 간선의 가중치가 각각 다른 그래프일 경우 -
다익스트라,벨만-포드(음수 가중치가 존재할 때) - 하나의 정점에서 다른 모든 정점까지 구하는 그래프일 경우 -
플로이드 와샬
이 최단 경로를 찾는 가장 대표적인 알고리즘이 바로 다익스트라 알고리즘입니다.
다익스트라 알고리즘은 기본적으로 다음과 같이 동작합니다.
- 출발 노드와 도착 노드, 가중치를 설정합니다.
- 최단 거리 테이블을 설정하는데, 이때, inf 같은 값으로 모든 노드들의 거리를 초기화하여 설정합니다.
- 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택합니다.
- 해당 노드를 거쳐 다른 노드를 가는 비용(가중치)을 계산하여 최단 거리 테이블을 갱신합니다.
- 3번과 4번을 반복하여 수행합니다.
이 다익스트라 알고리즘은 매번 선형 탐색을 하기 때문에, 시간이 오래 걸립니다. 그래서 우선순위가 가장 높은 데이터를 가장 먼저 꺼내는 자료구조인 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현합니다. 그리고 이 우선순위 큐를 구현하기 위해 최소 힙(Min Heap)과 최대 힙(Max Heap)이라는 자료구조가 사용됩니다.
이 다익스트라 알고리즘이 익숙치 않기 때문에 이를 이용한 기본적인 알고리즘 문제를 풀기 위해 백준에서 특정 거리의 도시 찾기라는 문제를 풀었습니다.
이 문제는 단순히 다익스트라 알고리즘 구현하여 해결하는 문제입니다.
아래는 문제에서 주어진 입력 코드와 결과 코드, 그 외 필요한 코드를 제외한 다익스트라 함수 구현부에 대해서만 설명하겠습니다.
JAVA
public class Main {
private static int N, M, K, X; // 도시의 개수, 도로의 개수, 거리 정보, 출발 도시의 번호
private static boolean[] visited = new boolean[N+1]; // 방문 표시
private static int[] d = new int[N+1]; // 최단 거리 테이블
public static void main(String[] args) {
...생략
Arrays.fill(d, Integer.MAX_VALUE); // 최단 거리 테이블의 모든 공간을 최댓값으로 초기화
d[X] = 0; // 출발 지점은 0
dijkstra(); // 다익스트라 호출
...생략
}
// 다익스트라
public static void dijkstra() {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(X, 0));
while (!pq.isEmpty()){
Node node = pq.poll();
int now = node.end;
// 방문하지 않았으면
if(!visited[now]){
visited[now] = true;
// 인접한 노드 탐색
for(Node n : list.get(now)){
// 어떤 노드를 거쳐가는 거리 값보다 그냥 도착 지점으로 가는 거리 값이 크다면
if(d[n.end] > d[now] + n.distance){
d[n.end] = d[now] + n.distance; // 최단 거리 갱신
pq.add(new Node(n.end, d[n.end]));
}
}
}
}
}
}
우선순위 큐를 선언하여 우선순위 큐에 시작 노드, 가중치로 저장합니다. (Node라는 클래스에 Comparable<>를 상속받아compareTo() 메서드를 가중치가 가장 짧은 순으로 정렬하도록 재정의하여 구현합니다.)
삽입된 데이터(노드, 가중치)를 꺼내면서 그에 인접한 노드들을 확인하면서 최단 거리 테이블(d)과 현재 노드를 거쳐서 다른 노드로 이동하는 거리를 비교하여 더 짧은 거리를 갱신하면서 큐에 삽입하는 과정을 반복합니다.
그러면 최단 거리 테이블에는 출발지인 X 노드에서 도착 노드까지의 최단 거리가 갱신됩니다.
Python
import sys, heapq
distance = [inf] * (n + 1)
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
# 다음에 가야하는 노드의 거리가 거리 정보가 저장된 distance[now]보다 크다면 넘기기
if distance[now] < dist:
continue
# 인접 노드 탐색
for next_node in graph[now]:
# distance 리스트에 저장된 값보다 현재 노드를 거쳐간 거리가 작다면
if dist + next_node[1] < distance[next_node[0]]:
# 거리 정보 갱신
distance[next_node[0]] = dist + next_node[1]
heapq.heappush(q, (dist + next_node[1], next_node[0]))Python 또한 JAVA와 비슷하지만, 우선순위 큐를 힙을 사용한 heapq 로 사용합니다.
이 heapq는 가장 작은 원소를 정렬 알고리즘을 사용하지 않고 가장 먼저 꺼낼 수 있습니다.
heapq에 튜플 형태인 (가중치, 노드번호)로 push하는데, 이는 가중치 값을 기준으로 가장 작은 값을 먼저 꺼낼 수 있게 합니다.
이상으로 이번 주에는 다익스트라 알고리즘에 대해서 공부하고 기본적인 알고리즘 문제들을 풀었습니다.
