[Java Algorithm Note] 다익스트라 (feat. BOJ #1753 최단경로)

오늘은 그래프, 그리디를 활용하는 다익스트라 알고리즘에 대해 정리해보려구 한다.

이름은 너무너무 많이 들어봤지만, 한번도 제대로 공부해본적은 없는,,!!

 

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

다익스트라는 최단 경로를 찾을 수 있는 알고리즘 중 하나이다.

최단 경로
간선의 가중치가 있는 그래프에서, 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로

 

👉 다익스트라 알고리즘을 사용한다는 것은,

하나의 시작 정점에서 끝 정점까지의 최단 경로를 구한다는 것을 얘기한다.

 

아래 그림을 예로 보자.

A가 시작점이고 C가 목적지라고 할 때, 가장 먼저 A에 인접해있는 정점은 B와 C이다.

이 때 A가 C로 가기 위해서는 두 가지 선택지가 생긴다.

1. 바로 C로 가자!
2. B를 거쳐서 C로 가자!

위의 그림을 보면 C가 바로 인접해있음에도 불구하고,

간선의 가중치로 인해 B를 거쳐 C로 향하는 것이 더 최단 경로임을 알 수 있다.

 

위 예시의 경우 단순히 B정점 하나만을 거치면 되므로 간단해보이지만,

경우에 따라 매우 많은 숫자의 정점을 지나는 것이 더 최단 경로가 될 수 있다.

 

그럴 때에는 하나 하나 경로를 따져보는 것이 어려워질 수 있는데,

이 때 유용하게 사용할 수 있는 알고리즘이 바로 다익스트라 알고리즘! 👏

 

💥 주의 사항

그런데 다익스트라 알고리즘을 사용하기 위해서는 체크해야 할 점이 있다.

다익스트라는 '음'의 가중치를 허용하지 않는다.

따라서 음의 가중치를 포함하는 문제의 경우 벨만-포드 알고리즘을 사용해야 한다.

 

이 외에도 플로이드-워샬 같은 알고리즘을 이용하면

좀 더 효율적으로 모든 정점들에 대한 최단 경로를 탐색하는 것도 가능한데,

벨만 포드와 플로이드 워샬은 다음에!! 다뤄보도록 하겠다.

---

📎 다익스트라 알고리즘 구현

나는 백준 사이트의 #1753 최단 경로 문제를 구현하는 코드로 작성했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_1753 {
	
	static class Node {
		int to, weight;
		
		public Node(int to, int weight) {
			this.to = to;
			this.weight = weight;
		}
	}
	
	static int V, E, S;
	static List<Node>[] list;
	static int[] dis;
	static boolean[] visited;
	
	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		StringBuilder out = new StringBuilder();
		
		V = Integer.parseInt(st.nextToken()); // 정점 개수
		E = Integer.parseInt(st.nextToken()); // 간선 개수
		S = Integer.parseInt(in.readLine()) - 1; // 시작 정점
		
		dis = new int[V];
		visited = new boolean[V];
		list = new ArrayList[V];
		for(int i = 0 ; i < V ; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i = 0 ; i < E ; i++) {
			st = new StringTokenizer(in.readLine());
			int from = Integer.parseInt(st.nextToken()) - 1; // u
			int to = Integer.parseInt(st.nextToken()) - 1; // v
			int weight = Integer.parseInt(st.nextToken()); // 가중치
			
			list[from].add(new Node(to, weight)); // 유향 처리
		}
		
		Arrays.fill(dis, Integer.MAX_VALUE);
		dis[S] = 0; // 시작점만 0으로 만들기
		Dijk();
		
		for(int i = 0; i < V ; i++) {
			if(dis[i] == Integer.MAX_VALUE) out.append("INF" + "\n");
			else out.append(dis[i] + "\n");
		}
		
		System.out.print(out);
	}
	
	public static void Dijk() { // 다익스트라
		PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.weight, o2.weight)); // 가중치 기준 정렬
		pq.offer(new Node(S, 0));
		
		while(!pq.isEmpty()) {
			Node now = pq.poll();
			
			if(dis[now.to] < now.weight) continue;
			
			for(int i = 0; i < list[now.to].size(); i++) {
				Node next = list[now.to].get(i);
				
				if(dis[next.to] > now.weight + next.weight) {
					dis[next.to] = now.weight + next.weight;
					pq.offer(new Node(next.to, dis[next.to]));
				}
			}
		}
	}
}

/*
[test case]
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
*/

코드 상단에서부터 차례대로 설명해보겠다.

 

✔️ Node 클래스

하나의 정점을 표현하는 클래스를 만들어주었다.

to(가리키는 정점)와 weight(가리키는 정점까지의 가중치)이라는 정보를 가진다.

 

✔️ 다익스트라를 위한 준비물 list, dis, visited

list는 각 정점마다, 가리키는 정점들에 대한 정보를 가질 수 있도록 하는 역할을 한다.

dis는 각 정점마다 시작점에서부터 오는데 걸린 최단 가중치를 저장한다.

visited는 각 정점마다 방문한적 있는지 여부를 저장한다.

 

✔️ list 초기화

아래에 list 초기화가 완료된 모습을 그림으로 표현했다.

list의 '인덱스 == 정점 번호'라고 가정, 각 정점마다 가리키는 정점의 정보들을 저장해주었다.

이 문제의 경우 유향 그래프이므로, 출발하는 정점에 도착하는 정점의 정보만 저장해주면 된다.

 

✔️ 최단 경로 탐색 전, 준비

dis 배열은 계속해서 최솟값을 업데이트해주어야 하므로 Intger.MAX_VALUE로 모두 채워주었다.

시작점에 해당하는 인덱스에는 0을 저장해주었다. (자기 자신에게 가는 거리는 당연히 0이 최소니까!)

 

✔️ 최단 경로 탐색 Dijk() 메서드

[1] PriorityQueue를 이용한 정점마다의 최소 경로 탐색

Node 타입으로 PriorityQueue를 만들고, weight(가중치)를 기준으로 정렬하도록 했다.

그리고 시작점에 대한 정보는 본격적인 탐색 시작 전 추가했다.
(*꼭 우선순위 큐를 사용해야 하는 것은 아니지만, 매 번 최소가 되는 것만 필요한 경우

우선순위 큐를 사용하는 것이 대부분 가장 효율적이므로!! 이렇게 해주는 것이 가장 좋아용)

 

[2] pq가 빌 때까지 탐색

• pq의 첫 번째 요소(pq에 저장된 정점 중 가장 작은 가중치를 가지는 정점)부터 꺼내어 now에 담았다.
• now가 가리키는 정점의 최단 경로(dis[now.to])가 now의 가중치보다 작다면 continue 했다.
  (=> 어차피 이 경로는 최단이 될 수 없는 것이므로!)
• 그 외의 경우에는 now가 가리키는 정점의 list를 돌면서 최단 경로를 탐색했다.
  가장 먼저 now가 가리키는 정점인 now.to가 가리키는 정점인 list[now.to].get(i)에 대한 정보를 next에 담았다.
  만약 dis[next]가 now의 가중치과 next의 가중치를 합한 것보다 크다면 dis[next]를 업데이트 해주었고,
  그 다음의 경로 또한 탐색해볼 가치가 있는 것으로 판단하여 다음 탐색을 위한 정보를 pq에 추가했다.

---

👀 정리

다익스트라는 양의 가중치만을 가지는 최단 경로 탐색에 유용한 알고리즘이다.

매 탐색마다 더 적합한 경로를 찾아나가는 방식으로 구현할 수 있으며,

우선순위 큐를 이용하면 더 효율적일 수 있다.

 

✍ 추가

문제를 더 풀어보다보니,, 그냥 BFS로 푸는데,

Queue 대신 PriorityQueue로 사용한다고 생각하니까 훨씬 이해가 쉬웠다 !!