[ 목차 ]
1. 정의
2. 다익스트라가 DP를 사용하는 이유
3. 코드 구현 예제 풀이 : 최소비용 구하기
4. 다익스트라의 탐색 방법
5. 정리
▶ 다익스트라 (데이크스트라, Dijkstra)
- 최단경로 탐색 알고리즘
- 인공위성 GPS 소프트웨어에서 사용한다. (최단경로 네비게이션)
- 특정 정점에서 모든 다른 정점까지 가는 최단경로를 탐색
- 위 작동 방식 때문에 이전에 알아본 DP를 이용한 탐색이 선호됨 (다이나믹 프로그래밍)
◈ 다익스트라가 DP를 사용하는 이유
최단거리는 최단거리들의 모임이기 때문이다.
즉, 이전까지의 최단거리 정보를 그대로 사용한다. ( = DP 배열에 저장한다)
한 정점에서 다른 정점으로의 최단거리는 탐색을 계속 진행할 때마다 새로 갱신된다.
이해를 돕기 위해 사진을 가져왔다.
알파벳은 정점이고, 숫자는 경로를 지나는 비용이다.
1) 정점 A에서 다른 지점으로의 최단경로 최초탐색시
2) 정점 B에서 다른지점으로의 최단경로 탐색시
3) 정점 C에서 다른지점으로의 최단경로 탐색시
4) 정점 D에서 다른지점으로의 최단경로 탐색시
위 과정에서 보이다시피 매 탐색마다 최단경로를 갱신하게 된다.
> 최단경로를 DP(배열)에 저장해 두었다가 비교하는 과정이 필요하다
▶코드 구현 예제 풀이 : 최소비용 구하기
이해를 돕기 위해, 백준의 1916번 문제 최소비용 구하기를 예시로 가지고왔다.
문제의 내용은 상술한 다익스트라 알고리즘의 예시와 비슷하다. 정점들이 주어지고, 각 정점을 지나는데 사용되는 비용이 입력된다.
핵심은 정점과 비용이 주어졌을 때, 실제적인 그래프의 구현을 어떻게 하느냐는 것이다.
그리고 해답은 이차원 배열에 있다..
바로 위에 사용한 예제 그래프를 정점을 숫자로 바꿔 다시 가져오겠다.
그리고 이차원 배열에, 각 정점을 행에 대응시키고, 정점에 대한 다른 정점으로의 비용을 열에 대응시킨다.
ex) 1행의 2열은 1 > 2로의 비용 3을 삽입. 1행 1열은 본인 스스로이기 때문에 비용 0
2행 3열은 2 > 3의 직행경로가 없기 때문에 불가 (무한, 혹은 최대 비용 초과로 표기)
| 0 | 3 | 2 | 6 |
| 3 | 0 | 불가 | 2 |
| 2 | 불가 | 0 | 1 |
| 6 | 2 | 1 | 0 |
문제 입력을 받아보자.
public class Main {
static boolean[] visited; //정점 방문여부 체크
static int[][] bus; //정점과 비용을 담을 이차원 배열
static int N,M;
static final int MAX = 100000001;//이동불가 비용 크기
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
N = Integer.parseInt(sc.nextLine());
M = Integer.parseInt(sc.nextLine());
visited = new boolean[N+1];
bus = new int[N+1][N+1];//이해의 편의성을 위해 행과 열의 인덱스를 1부터 시작
for(int i = 1; i<N+1; i++) {
for(int j = 1; j<N+1; j++) {
bus[i][j] = MAX;//전체를 이동불가 상태로 채우고 시작
}
}
for(int i = 0; i<M; i++) {
String[] temp = sc.nextLine().split(" ");
int depart = Integer.parseInt(temp[0]);
int arrival = Integer.parseInt(temp[1]);
int cost = Integer.parseInt(temp[2]);
if(cost < bus[depart][arrival]) {//비용 중복 입력 고려
bus[depart][arrival] = cost;//입력받은 비용만큼 지불하고 이동가능
}
}
int start= sc.nextInt();
int end = sc.nextInt();
int result = dijkstra(start,end);//다익스트라 구현 필요
System.out.println(result);
sc.close();
}
}
첫번째로 고려해야 하는 부분은 이동불가 비용의 크기인데, 문제에서 정점의 최대갯수는 1000이고, 비용의 최대 숫자는 100000이므로, 1000 * 100000 = 1억초과의 숫자를 사용해야한다.
두번째로 고려해야 하는 부분은 간선사이 이동 비용 중복입력인데, if문을 이용하여 최솟값만을 갱신하여 삽입하도록 한다.
다음은 다익스트라 부분의 구현이다.
//한 지점에서 최소비용으로 갈수있는 지점 탐색
public static int minCostIndex(int[] cost) {
int min = MAX;
int index = 0;
for(int i = 1; i<N+1; i++) {
if(cost[i] < min && !visited[i]) {
min = cost[i];
index = i;
}
}
return index;
}
//다익스트라 탐색(갱신 탐색)
public static int dijkstra(int start,int end) {
int[] dp = new int[N+1];//dp배열 생성(start 행에 대한 배열)
for(int i = 1; i<N+1; i++) {
dp[i] = bus[start][i];
}
visited[start] = true;
for(int i = 0; i < N-2; i++) {//시작지점과 최초방문지점을 제외한 나머지 지역 탐색횟수
int now = minCostIndex(dp);//현재 행에서 가장 최소비용 탐색
visited[now] = true;//최소비용 지점 방문
for(int j= 1; j<N+1; j++) {
if(!visited[j]) {
//start에서 j를 방문하는 비용이 start에서 now를 거쳐 j를 방문하는 비용보다 크다면 최소비용 갱신
dp[j] = (bus[now][j] + dp[now] < dp[j]) ? bus[now][j] + dp[now] : dp[j];
}
}
}
return dp[end];//출발지점부터 도착지점까지의 최소비용 반환
}
첫번째로 고려해야 하는 부분은 DP의 활용이다. 출발 지점(행)에 대한 도착 지점까지의 비용을 담은 배열, 즉 이차원배열의 출발지점 행을 DP배열로 이용한다.
출발 지점부터 나머지 정점들을 순차 탐색하며 정점 방문 최소 비용을 갱신하여 DP배열에 저장한다.
두번째로 고려해야 하는 부분은 최소비용 지점 탐색이다. DFS.BFS탐색에서 사용했던 방문체크 배열 visited를 활용하여 아직 방문하지 않은 정점중 최소 비용으로 이동할수 있는 정점을 찾아 반환하는 minCostIndex함수를 따로 만들어주었다.
(Visted 함수를 사용하여 모든 정점을 방문하기 때문에, 사실 BFS탐색이라고 보는 것이 맞겠다.)
세번째로 고려해야 하는 부분은 완전탐색을 통한 다익스트라 탐색 구현이다. for 이중 반복문 구조를 이용해 시작지점과 최초방문지점을 제외한 나머지 지역을 BFS 탐색 (완전탐색)하며 정점 방문 최소비용을 갱신하도록 구현한다.
▶전체 코드
import java.io.*;
import java.util.*;
public class Main {
static boolean[] visited;
static int[][] bus;
static int N,M;
static final int MAX = 100000001;//이동불가 크기
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
N = Integer.parseInt(sc.nextLine());
M = Integer.parseInt(sc.nextLine());
visited = new boolean[N+1];
bus = new int[N+1][N+1];//이해의 편의성을 위해 행과 열의 인덱스를 1부터 시작
for(int i = 1; i<N+1; i++) {
for(int j = 1; j<N+1; j++) {
bus[i][j] = MAX;
}
}
for(int i = 0; i<M; i++) {
String[] temp = sc.nextLine().split(" ");
int depart = Integer.parseInt(temp[0]);
int arrival = Integer.parseInt(temp[1]);
int cost = Integer.parseInt(temp[2]);
if(cost < bus[depart][arrival]) {//비용 중복 입력 고려
bus[depart][arrival] = cost;//입력받은 비용만큼 지불하고 이동가능
}
}
int start= sc.nextInt();
int end = sc.nextInt();
int result = dijkstra(start,end);
System.out.println(result);
sc.close();
}
//한 지점에서 최소비용으로 갈수있는 지점 탐색
public static int minCostIndex(int[] cost) {
int min = MAX;
int index = 0;
for(int i = 1; i<N+1; i++) {
if(cost[i] < min && !visited[i]) {
min = cost[i];
index = i;
}
}
return index;
}
//다익스트라 탐색(갱신 탐색)
public static int dijkstra(int start,int end) {
int[] dp = new int[N+1];//dp배열 생성(start 행에 대한 배열)
for(int i = 1; i<N+1; i++) {
dp[i] = bus[start][i];
}
visited[start] = true;
for(int i = 0; i < N-2; i++) {//시작지점과 최초방문지점을 제외한 나머지 지역 탐색횟수
int now = minCostIndex(dp);//현재 행에서 가장 최소비용 탐색
visited[now] = true;//최소비용 지점 방문
for(int j= 1; j<N+1; j++) {
if(!visited[j]) {
//start에서 j를 방문하는 비용이 start에서 now를 거쳐 j를 방문하는 비용보다 크다면 최소비용 갱신
dp[j] = (bus[now][j] + dp[now] < dp[j]) ? bus[now][j] + dp[now] : dp[j];
}
}
}
return dp[end];
}
}
▶출력 결과
입력 부분에서 설명한 두 가지 고려할 부분을 생각하지 못해 두번 틀렸다 (...)
◈ 다익스트라의 탐색 방법
정말 중요한 점이 하나 있는데, 나는 완전탐색을 이용하여 다익스트라 탐색을 진행했지만, 보통은 우선순위 큐를 이용하여 구현하는 것이 더 빠르고, 효율적이다.
특히 정점에 대응하는 간선의 갯수가 비정상적으로 적을 경우, 완전탐색은 더욱 힘을 잃게되고 비효율적이다.
우선순위 큐를 이용한 문제풀이는 다음시간에 우선순위 큐에 대해 알아보고 진행하겠다.
▶정리
- 다익스트라 (데이크스트라)는 최단거리 탐색에 이용되는 알고리즘이다.
- 다이나믹 프로그래밍을 활용하여 최단거리를 갱신하며 탐색을 진행한다.
- 탐색 방법은 BFS탐색을 이용한 완전탐색과 우선순위 큐를 이용한 최소 힙 탐색이 있는데, 보편적으로 우선순위 큐를 이용한 최소 힙 탐색이 빠르고 효율적이다.
'모각코' 카테고리의 다른 글
| [백엔드]자바 스프링부트 이해하기 (0) | 2025.01.29 |
|---|---|
| [알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기 (0) | 2024.08.04 |
| [알고리즘] 백트래킹(Back Tracking) 이해하기 (0) | 2024.07.28 |
| [알고리즘] 브루트 포스(Brute Force) 이해하기 (1) | 2024.07.21 |
| [알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 이해하기 (1) | 2024.07.20 |
