다익스트라(Dijkstra)
하나의 정점에서 출발했을 때 다른 모든 정점으로 최단 경로를 구하는 알고리즘
매번 가장 적은 비용을 가진 노드를 하나씩 꺼낸 다음 그 노드를 거쳐가는 비용, 즉 가장 적은 비용을 하나씩 선택하는 로식으로 구성되어 있음.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 1 | null | 2 | null |
| 2 | 1 | 0 | 3 | null | 2 |
| 3 | null | 3 | 0 | null | 1 |
| 4 | 2 | null | null | 0 | 2 |
| 5 | null | 2 | 1 | 2 | 0 |
다음과 같은 그래프가 존재할 때의 모든 경로를 표시함.
이때 null은 서로 연결이 안된 부분이며, 이럴 경우는 다른 곳을 경유해서 가는 루트의 길이의 최솟값을 넣어야 함.
1번 노드만 입력하면 아래와 같아짐.
| 0 | 1 | 4 | 2 | 3 |
|---|
다음 예시에서는 그렇지 않지만 서로 연결된 루트보다 어딘가를 경유해서 가는 루트가 더 짧을 수 있기 때문에 그 부분도 검사를 해줘야 함.
다익스트라 코드 with PriorityQueue
- 다익스트라 알고리즘은 우선순위 큐 + BFS의 형태를 지니고 있음.
- 각 정점까지의 최단 거리를 저장하는 배열 dp[]를 유지하며, 정점을 방문할 대마다 인접한 정점을 모두 검사함.
public class Main {
static List<Node>[] list; // 배열 maps의 데이터를 알맞게 저장
static int[] dp; // 최소 루트 저장
static boolean[] visited; // 방문 여부
public static void main(String[] args) {
int[][] maps = {{1, 2, 1}, {2, 3, 3}, {3, 5, 1}, {2, 5, 2},
{1, 4, 2}, {4, 5, 2}}; // 연결된 노드와 그 길이
int n = 5; // 노드 개수
// 배열 초기화
visited = new boolean[n+1];
dp = new int[n+1];
list = new ArrayList[n+1];
for (int i = 1; i <= n; i++) {
list[i] = new ArrayList<>();
}
// list에 maps 데이터 저장
for (int i = 0; i < maps.length; i++) {
int a = maps[i][0];
int b = maps[i][1];
int c = maps[i][2];
list[a].add(new Node(b,c));
list[b].add(new Node(a,c));
}
// 노드 1부터 시작하는 다익스트라 알고리즘
dijkstra(1);
// 노드에 대한 모든 최솟값 출력
for (int num : dp) {
System.out.print(num +" ");
}
}
// Dijktstra 알고리즘 (우선순위 큐(Heap)을 이용한 알고리즘)
static void dijkstra(int start) {
Queue<Node> q = new PriorityQueue<>();
Arrays.fill(dp, Integer.MAX_VALUE); // dp를 최솟값을 받을 수 있도록 초기화
q.add(new Node(start, 0)); // 1부터 시작할 수 있도록 데이터 추가
dp[start] = 0; // 1에서 1에 도달하는 거리는 0
while (!q.isEmpty()) {
Node node = q.poll();
int to = node.to; // 도착점(시작점) 선언
if (visited[to]) continue; // 이 노드에 방문했는지 여부 확인
else visited[to] = true; // 방문하지 않았으면 방문 표시
for (Node nxt : list[to]) { // 도착점(시작점)과 연결되어 있는 점에 대한 계산
if (dp[nxt.to] >= dp[to] + nxt.distance) { // 현재 저장된 값이 최솟값이 아니라면
dp[nxt.to] = dp[to] + nxt.distance; // 최솟값이 저장되도록 함.
q.add(new Node(nxt.to, dp[nxt.to])); // 도착점(시작점) 추가
}
}
}
}
}
class Node implements Comparable<Node>{
int to;
int distance;
Node(int to, int distance){
this.to = to;
this.distance = distance;
}
// Comparable<Node> 인터페이스를 사용하므로 반드시 넣어줘야 함.
@Override
public int compareTo(Node o) {
return Integer.compare(this.distance, o.distance);
}
}[결과]
프로그래머스 Lv. 2 배달
다음과 같은 문제는 DFS나 BFS로도 풀 수 있지만 그럴 경우 객체를 생성하여 마을과 마을 사이의 거리가 같이 저장되도록 해야 함.
그렇게 푸는 방법도 있지만 다음의 문제는 단일 시작점을 기준으로 구하는 다익스트라에 적절한 문제이므로 이 알고리즘으로 풀어보겠음.
import java.util.*;
class Solution {
int count, n, k;
List<Node>[] list;
int[] dp;
int[][] arr;
boolean[] visited;
public int solution(int N, int[][] road, int K) {
int answer = 0;
count = 0;
n = N;
k = K;
dp = new int[N+1];
arr = new int[N+1][N+1];
visited = new boolean[N+1];
list = new ArrayList[N+1];
for (int i = 1; i <= N; i++) {
list[i] = new ArrayList<>();
}
for (int i = 0; i < road.length; i++) {
int a = road[i][0];
int b = road[i][1];
int c = road[i][2];
list[a].add(new Node(b, c));
list[b].add(new Node(a, c));
}
dijkstra(1);
answer = count;
return answer;
}
private void dijkstra(int start) {
Queue<Node> q = new PriorityQueue<>();
q.add(new Node(start, 0));
Arrays.fill(dp, Integer.MAX_VALUE);
dp[start] = 0;
while (!q.isEmpty()) {
Node node = q.poll();
int to = node.to;
if (visited[to]) continue;
visited[to] = true;
for (Node nxt : list[to]) {
if (dp[nxt.to] >= dp[to] + nxt.distance) {
dp[nxt.to] = dp[to] + nxt.distance;
q.add(new Node(nxt.to, dp[nxt.to]));
}
}
}
for (int i = 1; i <= n; i++) {
if (dp[i] <= k) count++;
}
}
}
class Node implements Comparable<Node>{
int to;
int distance;
Node(int to, int weight){
this.to = to;
this.distance = weight;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.distance, o.distance);
}
}위의 코드에서 문제의 조건인 k를 넘지 않는 수만 카운트하는 부분만 추가함.
참고 자료
뭐라도 하자