안녕하세요 Coding-Knowjam입니다.
오늘은 다익스트라(Dijkstra) 알고리즘을 알아보겠습니다.
이론과 더불어 실제 구현을 백준 온라인 저지에 있는 문제풀이와 함께 할 예정이므로 문제를 미리 읽고 오시길 바라겠습니다.
https://www.acmicpc.net/problem/1753
1. 다익스트라(Dikstra) 알고리즘이란?
다익스트라(Dijkstra) 알고리즘은 방향성을 가지는 그래프에서 최단거리를 구할 때 자주 쓰입니다.
방향성을 가지는 그래프란 A에서 B노드로 이동은 가능하지만, B노드에서 A노드로는 이동할 수 없는 경우가 있는 그래프를 말합니다.
즉, 노드 간의 연결된 간선이 방향과 거리 비용을 가지고 있고, 시작 노드에서 다른 노드들까지의 최단거리 비용을 구할 때 사용할 수 있습니다.
다익스트라(Dijkstra) 알고리즘의 진행순서는 다음과 같습니다.
- 거쳐 갈 혹은 시작할 노드를 방문 후 방문 처리합니다.
- 방문한 노드에서 이동할 수 있는 노드들을 탐색합니다.
- 탐색된 노드들의 계산된 거리 비용이 현재까지 저장된 최단거리보다 적을 경우 최단거리를 갱신합니다.
- 최단거리가 갱신된 노드들 중 가장 작은 거리를 가지는 노드로 이동 후 방문 처리합니다.
- 1~4번을 계속 반복 후 더 이상 방문할 노드가 없을 때 종료됩니다.
글로만 보면 이해가 되지 않으실 테니 예시 그래프와 같이 진행순서를 살펴보겠습니다.
위의 그래프를 보면 노드 간에 연결된 간선들이 방향성을 가지고 있고 각 간선들마다 거리 값이 있는 것을 알 수 있습니다.
출발 노드는 1번이고, 1번 노드에서 다른 노드들까지 이동할 때의 최단거리를 구한다고 가정하고 다익스트라(Dijkstra) 알고리즘을 진행해보겠습니다.
우선 1번 노드를 방문 처리한 후 다른 노드들까지의 거리를 계산하기 위한 최단거리 테이블을 만들어주겠습니다.
최초에 최단거리 테이블을 작성할 때 시작 노드를 제외한 모든 노드들의 최단거리 값은 INF이고 시작 노드의 값은 0으로 초기화됩니다. (INF값은 간선이 가질 수 있는 거리 비용의 최댓값보다 항상 크다고 가정합니다.)
2번과 3번 노드는 그래프에서 보시는 것처럼 각 간선의 거리 값으로 최단거리 테이블을 갱신해주었습니다.
4번과 5번 노드는 현재 1번 노드에서 방문할 수 없으므로 INF값으로 불가능을 나타내 주었습니다.
방문처리가 된 노드는 노란색으로 표시해주었습니다.
갱신 여부는 FALSE, TRUE로 표시해주었습니다.
이제 최단거리가 갱신된 노드들 중에서 가장 작은 최단거리를 가지는 노드로 이동합니다.
위의 예시에서는 2번 노드가 3번 노드보다 값이 더 적으므로 2번 노드로 이동 후 방문 처리합니다.
2번 노드를 방문한 후에는 이동 가능한 노드들을 탐색 후 최단거리 테이블을 갱신해줘야 합니다.
현재 2번 노드에서 방문 가능한 노드는 3번과 4번 노드가 있습니다.
그러나 3번 노드는 1번->3번으로 갈 때의 거리 비용이 1번->2번->3번으로 이동할 때의 거리 비용 값보다 적으므로 갱신되지 않습니다.
이를 최단거리 테이블 관점에서 살펴보면 다음과 같이 표현할 수 있습니다.
최단거리 테이블 3번 노드 값 < 최단거리 테이블 2번 노드 값 + 2번 노드에서 3번 노드로 이동할 때의 간선의 거리
결국 좌측의 값이 우측보다 클 때만 최단거리가 경신된다고 할 수 있습니다.
이어서 살펴보겠습니다.
4번 노드는 1번 노드에서 이동이 불가능했지만 2번 노드를 거쳐갈 때는 이동이 가능하므로 1번->2번->4번 노드로 연결되는 간선의 거리 비용 값을 모두 더한 값으로 갱신해줍니다.
이를 최단거리 테이블 관점에서 살펴보겠습니다.
최단거리 테이블 4번 노드 값 > 최단거리 테이블 2번 노드 값 + 2번 노드에서 4번 노드로 이동할 때의 간선의 거리
이번에는 좌측의 값이 우측의 값보다 크기 때문에 최단거리 테이블이 갱신되었습니다. (INF는 간선이 가질 수 있는 거리의 최댓값보다 큰 값입니다.)
이제 최단거리가 갱신된 노드 중 가장 적은 거리를 가지는 노드로 이동을 합니다.
위의 그림에서는 1번 노드를 방문했을 때 갱신되었던 3번 노드가 4번 노드보다 거리 값이 적으므로 3번 노드로 이동하겠습니다.
3번 노드를 방문 처리 후에 이동 가능한 노드를 탐색하면 현재 4번 노드로만 이동이 가능합니다.
최단거리 테이블 갱신을 위해 최단거리 값을 계산해보겠습니다.
최단거리 테이블 4번 노드 값 < 최단거리 테이블 3번 노드 값 + 3번에서 4번 노드로 이동할 때의 거리
좌측의 값보다 우측의 값이 크기 때문에 4번 노드의 최단거리는 갱신되지 않습니다.
이제 현재까지 최단거리가 갱신된 노드 중에서 거리가 가장 작은 노드로 이동을 진행합니다.
현재 갱신된 노드 목록에서 남아있는 노드는 4번 노드 1개뿐이므로 4번으로 이동합니다.
4번 노드를 방문 처리한 후에 이동 가능한 노드를 탐색합니다.
현재 4번 노드에서 다른 노드들로 이동 가능한 간선이 존재하지 않기 때문에 최단거리 테이블을 갱신하는 작업은 진행되지 않습니다.
다음으로 현재까지 갱신된 노드들 중에서 가장 작은 거리 값을 가지는 노드를 찾습니다.
그러나 갱신된 노드 목록이 비어있으므로 더 이상 방문할 노드가 존재하지 않다는 걸 알 수 있습니다.
방문할 노드가 존재하지 않으면 알고리즘을 종료합니다.
알고리즘이 종료된 시점에서 최단거리 테이블의 값은 시작 노드에서 다른 모든 노드들을 방문할 때의 최단거리를 의미합니다.
위의 예시에서 5번 노드를 제외하고는 모두 방문이 가능했고, 5번 노드는 1번 노드에서 이동할 수 있는 방법이 없으므로 불가능을 의미하는 INF값을 가집니다.
이제 알고리즘이 어떻게 진행되는지 확인을 했으니 코드로 한번 구현해 보겠습니다.
2. Java 코드로 구현
코드로 구현할 때 유의하셔야 할 점이 몇 가지 있습니다.
우선 그래프를 표현할 때 보통은 2차원 배열로 선언을 많이 하는데, 2차원 배열보다는 List컬렉션을 통해서 구현하는 것을 추천드립니다.
왜냐면 모든 노드가 간선으로 연결된 것이 아니라면 2차원 배열은 간선이 존재하지 않는 경우의 값도 저장하지만, 2차원 List로 표현을 하면 간선이 존재하는 노드들끼리의 연결만 표현할 수 있기 때문입니다.
또한 위의 설명에서 보셨던 갱신된 노드들의 목록을 저장할 때는 우선순위 큐를 사용하셔야 합니다.
왜냐면 처음에 갱신되었던 노드보다 나중에 갱신되었던 노드의 최단거리 값이 더 작다면 나중에 갱신되었던 노드로 방문을 진행해야 하는데 일반적은 배열에 담으면 최단거리를 기준으로 오름차순 정렬을 따로 코드로 작성해줘야 하기 때문입니다.
우선순위 큐를 사용할 때 정렬 기준을 최단거리의 오름차순으로 미리 지정해 논다면 추후에 큐에 offer() 되는 노드들은 최단거리를 기준으로 값이 자동으로 정렬되므로 poll()로 꺼내기만 하면 다음에 방문할 노드의 인덱스를 바로 알 수 있어서 구현할 때 매우 효과적입니다.
그리고 INF의 값은 전체 노드의 개수 * 간선이 가질 수 있는 최대의 거리 비용 값보다 크게 잡으셔야 합니다.
시작 노드에서 하나씩 거쳐서 제일 마지막에 있는 노드에 도달할 때 가질 수 있는 간선의 거리 비용의 최댓값보다 INF의 값이 커야 최단거리 테이블을 갱신할 수 있기 때문입니다.
그럼 맨 처음에 말씀드렸다시피 백준 온라인 저지에 있는 문제를 통해 구현을 해보겠습니다.
문제를 아직 안 보셨다면 링크를 통해서 문제를 확인하고 오시길 바라겠습니다.
graph를 표현하는 List와 우선순위 큐에 모두 사용할 Node클래스를 만들어주겠습니다.
// 우선순위 큐에서 정렬기준을 잡기위해 Comparable를 구현합니다.
static class Node implements Comparable<Node>{
int index; // 노드 번호
int distacne; // 이동 할 노드까지의 거리
Node(int index, int distacne) {
this.index = index;
this.distacne = distacne;
}
// 최단거리를 기준으로 오름차순 정렬합니다.
@Override
public int compareTo(Node o) {
return Integer.compare(this.distacne, o.distacne);
}
}
main메서드와 함께 전체적인 소스를 작성해보겠습니다.
package study.blog.codingnojam.algorithm;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class BOJ_1753 {
// INF 값 초기화
static final int INF = 9999999;
// 그래프를 표현 할 2차원 List
static List<List<Node>> graph = new ArrayList<>();
// 최단거리테이블을 표현 할 배열
static int[] result;
// 방문처리를 위한 배열이지만 저는 다른 방법으로 방문처리를 진행하겠습니다.
// static boolean[] vistied;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] info = br.readLine().split(" ");
int startIndex = Integer.parseInt(br.readLine());
// 그래프 생성
for (int i = 0; i < Integer.parseInt(info[0])+1; i++) {
graph.add(new ArrayList<>());
}
// 최단거리테이블 생성
result = new int[Integer.parseInt(info[0])+1];
// 최단거리테이블 INF로 초기화
Arrays.fill(result, INF);
// 방문처리를 위한 배열 생성 (저는 사용하지 않습니다)
// vistied = new boolean[Integer.parseInt(info[0])+1];
// 문제에서 주어진 입력 값에 따라 그래프 초기화
for (int i = 0; i < Integer.parseInt(info[1]); i++) {
String[] temp = br.readLine().split(" ");
graph.get(Integer.parseInt(temp[0])).add(new Node(Integer.parseInt(temp[1]), Integer.parseInt(temp[2])));
}
// 문제에서 주어진 입력값을 바탕으로 다익스트라 알고리즘 수행
dijkstra(startIndex);
// 문제에서 제시한 조건에 맞게 출력
for (int i = 1; i < result.length; i++) {
if(result[i] == INF) {
bw.write("INF");
bw.newLine();
}else {
bw.write(String.valueOf(result[i]));
bw.newLine();
}
}
bw.flush();
}
// 다익스트라 알고리즘
static void dijkstra(int index) {
// 최단거리가 갱신 된 노드들을 담을 우선순위 큐 생성
PriorityQueue<Node> pq = new PriorityQueue<>();
// 최단거리테이블의 시작지점노드 값 0으로 갱신
result[index] = 0;
// 우선순위 큐에 시작노드 넣기
pq.offer(new Node(index, 0));
// 우선순위 큐에 노드가 존재하면 계속 반복
while(!pq.isEmpty()) {
// 큐에서 노드 꺼내기
Node node = pq.poll();
// 꺼낸 노드의 인덱스 및 최단거리 비용 확인
int nodeIndex = node.index;
int distance = node.distacne;
// 앞에서 주석처리했던 방문처리 배열을 사용해서 아래와 같이 방문처리하셔도 됩니다.
// if(vistied[nodeIndex]) {
// continue;
// }else{
// vistied[nodeIndex] = true;
// }
// 큐에서 꺼낸 거리와 최단거리테이블의 값을 비교해서 방문처리를 합니다.
// 큐는 최단거리를 기준으로 오름차순 정렬되고 있습니다.
// 만약 현재 꺼낸 노드의 거리가 최단거리테이블의 값보다 크다면 해당 노드는 이전에 방문된 노드입니다.
// 그러므로 해당노드와 연결 된 노드를 탐색하지 않고 큐에서 다음 노드를 꺼냅니다.
if(distance > result[nodeIndex]) {
continue;
}
// 큐에서 꺼낸 노드에서 이동 가능 한 노드들을 탐색합니다.
for (Node linkedNode : graph.get(nodeIndex)) {
// 해당노드를 거쳐서 다음 노드로 이동 할 떄의 값이 다음 이동노드의 최단거리테이블 값보다 작을 때
if(distance + linkedNode.distacne < result[linkedNode.index]) {
// if문의 조건을 만족했다면 최단거리테이블의 값을 갱신합니다.
result[linkedNode.index] = distance + linkedNode.distacne;
// 갱신 된 노드를 우선순위 큐에 넣어줍니다.
pq.offer(new Node(linkedNode.index, result[linkedNode.index]));
}
}
}
}
// 우선순위 큐에서 정렬기준을 잡기위해 Comparable를 구현합니다.
static class Node implements Comparable<Node>{
int index; // 노드 번호
int distacne; // 이동 할 노드까지의 거리
Node(int index, int distacne) {
this.index = index;
this.distacne = distacne;
}
// 최단거리를 기준으로 오름차순 정렬합니다.
@Override
public int compareTo(Node o) {
return Integer.compare(this.distacne, o.distacne);
}
}
}소스에 대한 설명은 각 코드마다 주석을 통해서 설명하고 있으니 읽어보시길 바랍니다.
복잡하게 느껴지실 수도 있지만 앞에서 설명드렸던 진행과정을 떠올리시면서 천천히 보시면 어렵지 않게 이해하실 수 있을 겁니다.
감사합니다.
'Algorithm & Data Structure > 이론' 카테고리의 다른 글
| [Algorithm] 유클리드 호제법을 Java로 구현해보자!! (with BOJ 2609) (1) | 2021.07.21 |
|---|---|
| [Algorithm] 세그먼트 트리(Segment Tree)를 Java로 구현해보자! !(with BOJ-2042 Java로 문제풀이) (0) | 2021.06.13 |
| [Algorithm] DFS (Depth-first Search)를 Java로 구현해보자! (7) | 2021.04.16 |
| [Algorithm] BFS(Breadth-first search)를 Java로 구현해보자! (3) | 2021.04.11 |
| [Algorithm] Trie를 Java로 구현해보자! (0) | 2021.04.10 |
댓글