다익스트라 X BOJ_4485_녹색옷입은애가 젤다지?

시작

다익스트라 개념에 대해 정리한것을 포스팅 합니다.

다익스트라는 기본적으로 최단 경로로 많이들 알고 있지만, 최단 경로는 BFS 로도 접근할 수 있기 때문에 여기서 최소 비용 개념을 추가해주어야 합니다. 

즉, 다이스트라는 최단 거리 + 최소 비용의 문제입니다.

 

조건

보통의 다익스트라의 문제 경우 아래 조건들을 만족합니다.

1. 방향 그래프 입니다.

2. 0 이상의 가중치 값을 가지고 있습니다

3. 사이클이 존재하지 않아야 합니다.

 

구현 (코드X)

다익스트라의 경우 BFS 개념에 그리디 알고리즘을 적용합니다. 

덧붙이면, 최단 거리를 구하게 되지만 매 순간 가장 좋은 가중치 값을 선택하게 됩니다. 

거리, 방문 여부 변수를 두어 다익스트라 알고리즘이 어떻게 동작하는지 살펴보겠습니다.

 

그림

처음 워크플로우는 거리값이 모두 최댓값을 저장하고 있습니다. (갱신되기 때문에 최댓값을 지정합니다.) 

마찬가지로, 방문여부도 모두 False 입니다. 

시작지점은 1 입니다. 

처음 고민해봐야 하는것은 1 자기자신에 대한 거리를 갱신하고 방문여부를 True로 변경하는 것입니다.

당연하겠지만 자기자신은 거리가 0 이기 때문에 0으로 갱신하게 됩니다. 

그 후엔 1과 연결된 노드를 살펴보게 됩니다.

빨간색 선으로 체크한 부분이 1과 연결된 노드 입니다.

2,3 이 이에 해당합니다. 

2,3 의 거리를 갱신합니다. 방문여부는 여전히 False 입니다. (1에서 바라보는 것이기 때문에 방문되진 않았습니다.)

1에서 3을 바라보는 값은 9 입니다. 최댓값보다 작으므로 9로 갱신하게 됩니다. 

2도 마찬가지로 1로 갱신합니다. 

2,3 중에 제일 거리 값이 작은 노드로 검색을 시작합니다. 

2 노드에서 탐색을 시작합니다. 

2와 연결된 노드는 3,4 입니다.

3의 경우 기존 값이 9 였으나,

1⇢2⇢3으로 이동할 경우 6이 기존 값 9보다 작기 떄문에 6으로 갱신하게 됩니다. 

이런 흐름으로 시작 지점(=1) 에서 도착 지점(=7) 까지 최단 거리와 최소 비용으로 알고리즘이 수행되게 됩니다. 

바로 작성한 내용을 기반으로 백준에서 풀어볼 수 있는 다익스트라 대표 문제를 해결해보겠습니다. 

BOJ_4485_녹색옷을 입은 애가 젤다지

이 문제에서 가장 핵심적인 요소는 문제에 설명되어 있는 하기 글입니다. 

"링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다."

우선 이동할 수 있는 거리가 1인 점에서 BFS를 적용할 수 있습니다. 또, 비용을 최소로 하기 때문에 양의 가중치내에서 다익스트라 알고리즘을 적용시킬 수 있습니다.

우선순위 큐를 활용한 다익스트라 알고리즘 구현

가장 핵심적인 코드는  cost[ddx][ddy] > map[ddx][ddy] + cost[x][y] 입니다. 

우선순위 큐를 사용한 점에서 Min-Heap을 사용할 수 있고, 매번 갱신 된 값이 최솟값으로 우선순위 큐의 맨위로 올라오게 됩니다. 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n;
    static int[][] map;
    static int[][] cost;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static class POS implements Comparable<POS>{
        int x;
        int y;
        int sum;
        POS(int x, int y, int sum){
            this.x = x;
            this.y = y;
            this.sum = sum;
        }
        @Override
        public int compareTo(POS o) {
            // TODO Auto-generated method stub
            return this.sum - o.sum;
            //내림차순
        }
        
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int isInput = -1;
        int k = 1;
        while(isInput !=0) {
            //처음 입력한 값은 무조건 들어감
            n = Integer.parseInt(br.readLine());
            if(n == 0) break;
            map = new int[n][n];
            for(int i=0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j=0; j<n; j++) {
                    //input
                    map[i][j] = Integer.parseInt(st.nextToken());
                }//end of first loop
            }//end of second loop
            cost = new int[n][n];
            
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    cost[i][j] = Integer.MAX_VALUE;
                    //최소금액을 찾고있으므로 맥스값을 셋팅한다. 
                }//end of first loop
            }//end of second loop
            
            cost[0][0] = map[0][0];
            //시작위치 init
            
            PriorityQueue<POS> q = new PriorityQueue<>();
            //최소 min 이 맨위로 올라갈 것임
            q.add(new POS(0,0,0));
            //1. x좌표, 2. y좌표, 3. sum 값
            while(!q.isEmpty()) {
                POS tempD = q.poll();
                int x = tempD.x;
                int y = tempD.y;
                
                //fetch
                
                for(int i=0; i<4; i++) {
                    int ddx = x + dx[i];
                    int ddy = y + dy[i];
                    //four directions
                    
                    if(ddx<0 || ddx>=n || ddy<0 || ddy>=n) continue;
                    
                    if(
                       cost[ddx][ddy] > map[ddx][ddy] + cost[x][y]
                            ) {
                        cost[ddx][ddy] = map[ddx][ddy] + cost[x][y];
                        //방문하지 않았고
                        //다음에 업데이트 할 값이 더 작고
                        q.add(new POS(ddx,ddy,cost[ddx][ddy]));
                    }
                }
            }
            System.out.println("Problem " +(k++)+": "+ cost[n-1][n-1]);
            
            
        }
    }
 
}