안녕하세요 이번 시간에는 다익스트라 알고리즘에 대해 알아보는 시간을 갖도록 하겠습니다. 다익스트라란 출발 노드와 모든 노드 간의 최단 거리를 탐색할 때 사용하는 알고리즘입니다. 시간 복잡도는 O(간선 수 Log(노드 수))이며 간선의 값은 모두 양수여야 합니다.
다익스트라 알고리즘은 다음의 과정으로 동작합니다.
1. 인접 리스트로 그래프 구현
2. 최단 거리 배열 초기화 : 출발 노드는 0으로 설정, 이외는 적당히 큰 값으로 초기화
3. 값이 가장 작은 노드 선택 : 최단 거리 배열에서 현재 값이 가장 작은 노드 선택
4. 최단 거리 배열 업데이트 : 선택된 노드에 연결된 간선의 값을 바탕으로 다른 노드 값 업데이트
- 연결 리스트를 이용해 현재 선택된 노드의 간선들을 탐색하고 업데이트
- 연결 노드의 최단 거리는 두 값 중 더 작은 값으로 업데이트
- 과정 3~4를 반복해 최단 거리 배열 완성
이 때 주의할 점은 방문한 노드는 패스한다는 점입니다. 특히나, bfs처럼 노드가 향하는 목적지 리스트를 탐색하면서 체크하는 것이 아닌 초기에 체크 작업을 진행해야 한다는 점입니다. 왜냐하면 목적지 리스트를 탐색하는 와중 체크를 진행 시 불필요한 중복 작업이 처리될 수 있기 때문입니다.
다익스트라 알고리즘의 구현은 1753(최단경로) 문제로 구현할 수 있습니다. 방향이 있는 인접 리스트와 최단 거리 배열, 그리고 체크 배열을 생성합니다. 이후 우선순위 큐를 생성하여 시작 위치를 큐에 추가합니다. 큐에서 값을 뽑으면서 방문한 노드면 패스, 방문하지 않으면 체크합니다. 현재 노드의 인접 리스트를 탐색하면서 다음 노드의 최단 거리가 이전 노드의 최던 거리에 다음 노드의 간선값의 합보다 크다면 다음 노드의 최단 거리를 이전 노드의 최던 거리에 다음 노드의 간선값의 합으로 대체 후 다시 큐에 추가합니다. 이후 방문한 노드라면 최단 거리 노드의 값을 리턴합니다. 이 때 주의할 점은 최단 거리 배열 초기화 시 0부터 초기화해야한다는 점입니다.
import java.util.*;
import java.io.*;
class Main{
static int V,E,K;
static List<Node>[] graph;
static int[] distance;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
K = Integer.parseInt(br.readLine());
graph = new List[V+1];
for(int i=1;i<=V;i++) graph[i] = new ArrayList<>();
distance = new int[V+1];
for(int i=0;i<=V;i++) distance[i] = Integer.MAX_VALUE;
distance[K] = 0;
for(int i=0;i<E;i++){
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
graph[u].add(new Node(v,w));
}
PriorityQueue<Node> queue = new PriorityQueue<>();
boolean[] check = new boolean[V+1];
queue.add(new Node(K,0));
while(!queue.isEmpty()){
Node curr = queue.poll();
int node = curr.node;
if(check[node]) continue;
check[node] = true;
for(Node tmp : graph[node]){
int next = tmp.node;
int value = tmp.edge;
if(distance[next] > distance[node] + value){
distance[next] = distance[node] + value;
queue.add(new Node(next, distance[next]));
}
}
}
StringBuilder sb = new StringBuilder();
for(int i=1;i<=V;i++){
if(check[i]) sb.append(distance[i]).append("\n");
else sb.append("INF").append("\n");
}
System.out.println(sb);
}
static class Node implements Comparable<Node>{
int node;
int edge;
Node(int node, int edge){
this.node = node;
this.edge = edge;
}
@Override
public int compareTo(Node o) {
return this.edge - o.edge;
}
}
}다익스트라 알고리즘은 간선값이 독립적으로 존재할 경우 출발 지점과 도착 지점 간의 최단 경로를 구하는 문제에서 사용됩니다.
백준 1916(최소비용 구하기) 문제의 경우 N개의 도시와 한 도시에서 다른 도시로 도착하는 M개의 버스가 있을 때 A 도시에서 B 도시까지 가는데 드는 버스 비용을 최소화하는 비용을 출력하는 문제입니다. 위에서 구현한 다익스트라 알고리즘을 구현하여 출발 노드 기준으로 다익스트라 알고리즘을 구현한 후 도착 노드의 최단 거리 배열을 출력합니다.
백준 1854(K번째 최단 경로 찾기) 문제의 경우 K번째 최단경로의 소요시간을 출력하는 문제입니다. 다익스트라 알고리즘을 구현하되 최단 거리 배열을 우선순위 큐의 1차원 배열로 구현합니다. 최단 거리 배열의 우선순위 큐의 크기를 K로 할당한 후 내림차순으로 정렬하면 우선순위 큐의 K번째 최단경로를 구할 수 있습니다. 이후 저장된 최단 비용의 수가 K개 이하일 경우 해당 최단비용에 현재 최단비용값을 추가하고 큐에 추가하며, 저장된 최단 비용의 수가 현재 최단 비용보다 클 경우 poll한 후 최단비용 배열 및 큐에 추가합니다.
