Dijkstra

Dijkstra

다익스트라(Dijkstra)

다익스트라는 출발점에서 목표점까지 최단거리를 구할 때 사용되는 알고리즘이다.

---

이 알고리즘의 특성은 우선순위 큐와 너비 우선 탐색을 먼저 이해하는 것이 좋다. 해당 알고리즘은 많은 경로 중 최소 값을 가지는 노드 먼저 방문하는 원리이다. 최소값을 비교하는데 우선순위 큐를, 탐색에는 너비 우선 탐색을 거친다.

다익스트라의 변수를 다음과 같이 가정하자.

boolean[] visit      //방문했는지 확인하는 변수
int[] cost      //최단거리를 저장하는 변수

1. visit은 전부 false, cost는 Integer.MAX_VALUE로 초기화하고, 시작노드의 cost를 0으로, visit을 true로 지정하여 시작한다.
2. 시작노드와 연결된 다른 노드들의 cost값 중 가장 작은 것 먼저 탐색을 시작한다.
3. 방문하지 않은 노드 중 cost가 가장 작은 노드에서 해당 노드를 거치는 경우와 거치지 않는 경우의 값을 비교한다.
4. 반복!

---

예시

아래와 같은 그래프가 있다. 1번 노드에서 6번 노드로 가는 최단 거리는?

다익스트라의 과정대로 천천히 살펴보자.

• visit은 전부 false, cost는 Integer.MAX_VALUE로 초기화하고, 시작노드의 cost를 0으로, visit을 true로 지정하여 시작한다.

• 시작노드와 연결된 다른 노드들의 값 중 가장 작은 것 먼저 탐색을 시작한다. (visit[2]=true)

• 방문하지 않은 노드 중 cost가 가장 작은 노드에서 해당 노드를 거치는 경우와 거치지 않는 경우의 값을 비교한다.

이때 visit을 통해서 해당 노드를 탐색했는지 확인하고, 최단거리를 갱신한다. cost[2]는 원래 Integer.MAX_VALUE 였는데, 이번 탐색으로 거리가 1으로 갱신된다. 그리고 이를 우선순위 큐에 넣는다.

다른 값도 탐색하며 우선순위 큐에 넣는다! (but visit은 갱신 X)

이를 반복한다…!

---

20046번: Road Reconstruction

import java.util.*;
import java.io.*;

class compar implements Comparable<compar>{
	int x; int y; int cost;
	compar(int x, int y, int cost){
		this.x=x; this.y=y; this.cost=cost;
	}
	public int compareTo(compar o1) {
		return this.cost-o1.cost;	
	}
}

public class Main {

	static int[][] field = new int[100][100];
	static boolean[][] visit = new boolean[100][100];
	static int[][] cost = new int[100][100];
	static int[] movex = {-1,1,0,0};
	static int[] movey = {0,0,-1,1};
	static int M, N;
	
	//갈수있는 모든 정보가 있는 경우, 가는 방향에 따라서 큐로 계속 진행되는 경우로 정리.
	static void Dijkstra() {
		visit[0][0]=true;
		cost[0][0]=field[0][0];
		PriorityQueue<compar> que = new PriorityQueue<compar>();
		que.add(new compar(0,0,0));
		while(!que.isEmpty()) {
			compar t = que.poll();
			int tx = t.x;
			int ty = t.y;
			visit[tx][ty]=true;
			for(int i=0; i<4; i++) {
				int px = tx + movex[i];
				int py = ty + movey[i];
				if (px>=0&&py>=0&&px<M&&py<N) {
					if(!visit[px][py]&&field[px][py]!=-1) {
						if(cost[px][py]>cost[tx][ty]+field[px][py]) {
							cost[px][py]=cost[tx][ty]+field[px][py];
							//visit[px][py]=true;
							que.add(new compar(px, py, cost[px][py]));
						}
					}
				}
			}
		}
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		M = sc.nextInt();
		N = sc.nextInt();
		field = new int[M][N];
		visit = new boolean[M][N];
		cost = new int[M][N];
		
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				field[i][j]=sc.nextInt();
				cost[i][j]=Integer.MAX_VALUE;
				if(field[i][j]==-1) {
					cost[i][j]=-1;
				}
			}
		}
		if(field[0][0]==-1) {System.out.println(-1); return;}
		
		Dijkstra();
		
		
		if(!visit[M-1][N-1]) {
			System.out.println(-1);
		}
		else {
			System.out.println(cost[M-1][N-1]);
		}
		
	}

}

---

• 결론! 코드만 보기

    class compar implements Comparable<compar>{
    	int x; int y; int cost;
    	compar(int x, int y, int cost){
    		this.x=x; this.y=y; this.cost=cost;
    	}
    	public int compareTo(compar o1) {
    		return this.cost-o1.cost;	
    	}
    }	
      
    static void Dijkstra() {
    		//1. 초기화
    		visit = new boolean[M][N];
    		for(int i=0; i<M; i++) {
    			for(int j=0; j<N; j++) {
    				cost[i][j]=Integer.MAX_VALUE;
    			}
    		}
      
    		visit[0][0]=true;
    		cost[0][0]=field[0][0];
    		PriorityQueue<compar> que = new PriorityQueue<compar>();
    		que.add(new compar(0,0,0));
      
    		while(!que.isEmpty()) {     //4. 반복!
    			compar t = que.poll();		//2. 작은 노드부터 우선순위 큐로!
    			int tx = t.x;
    			int ty = t.y;
    			visit[tx][ty]=true;
    			for(int i=0; i<4; i++) {
    				int px = tx + movex[i];
    				int py = ty + movey[i];
    				if (px>=0&&py>=0&&px<M&&py<N) {
    					if(!visit[px][py]&&field[px][py]!=-1) {
    						if(cost[px][py]>cost[tx][ty]+field[px][py]) { //3. 값 비교 후 갱신!
    							cost[px][py]=cost[tx][ty]+field[px][py];
    							//visit[px][py]=true;
    							que.add(new compar(px, py, cost[px][py]));
    						}
    					}
    				}
    			}
    		}
    	}
  

  1. visit은 전부 false, cost는 Integer.MAX_VALUE로 초기화하고, 시작노드의 cost를 0으로, visit을 true로 지정하여 시작한다.
  2. 시작노드와 연결된 다른 노드들의 cost값 중 가장 작은 것 먼저 탐색을 시작한다.
  3. 방문하지 않은 노드 중 cost가 가장 작은 노드에서 해당 노드를 거치는 경우와 거치지 않는 경우의 값을 비교한다.
  4. 반복!

  
  

---

• 부족했던 점..

  1916번: 최소비용 구하기

  
  

  

  수많은… 시행 착오 끝에.. ㅠㅠ

  왜 틀렸는 지 알게 되었다. 생각보다 visit을 처리하는 것이 가장 중요했던 것이다…!

  
  

  나는 que에 노드를 추가할 때 부터 해당 노드의 visit을 true로 해주어서 다른 경로에 더 짧은 거리를 가지는 경로가 있어도 갱신이 안되게 코드를 짠 것이다..

  

  
  

  4,3까지 탐색 후 우선순위 큐에 들어간 [2,3,4]에 대해서 가장 작은 비용인 2노드 부터 다시 탐색이 시작된다.

  

  
  

  1의 경우 visit[1]=true이기 때문에 방문이 불가하다. visit[4]=true이기 때문에 4번 노드도 탐색이 불가하다…. 하지만 만약 현재 주황색(탐색하는 경로가) 기존 cost[4] 보다 작다면…?!

  

  
  

  위와 같은 예시에서 1→4 노드까지 최단 거리는 1.5로 4번노드의 cost는 갱신되어야 한다…

  
  

  visit을 최소거리를 가지는 노드에만 시켜서… 이를 해결했다… 또는 que.poll(); 시에 방문을 체크하는 식으로 고쳤더니 맞더라…

  20046문제는 격자형에 조건이 걸려있어서 이런 문제가 안생겼던거 같다… 그래도 위에 코드는 고쳤다…! ㅠㅠ