[ 백준 ][ 자바 ][ 4485 녹색 옷 입은 애가 젤다지? ]

일단 

다익스트라 알고리즘과

우선순위 큐에 대해서 알고가야만 하는 상황이다.

그냥 dfs 문제인줄 알았는데 전혀 아니었다..

두개의 차이를 알아야하는게 필요 한 것 같다. 일단!

다익스트라 알고리즘은 

한 정점에서 시작해서 연결되어 있는 다른 정점을 탐색하는데

그 정점을 계속 업데이트 하면서 가장 짧은 길이를 저장하는 방식이다.

난 dp 를 잘 모르는데 그냥 비슷해보인다. 

일단 

3

5 5 4

3 9 1

3 2 7

라 했을경우 

 [0][0] - [0][1] - [0][2]

    |         |         |

 [1][0] - [1][1] - [1][2]

    |         |         |

 [2][0] - [2][1] - [2][2]

이런식으로 정점들이 이어져있고 각각 정점들 사이의 거리가 값이라 할수 있겠다.

한번 하나 하나 해보자

현재 dist 배열은 전부 무한대이다( int 최대값 ) 

map[0][0] = 5,

인접한 정점 map[0][1]  =5  , map [1][0] = 3  

dist[0][1] > dist[0][0] = 5 + map[0][1] = 5;  => dist[0][1] = 10 add

dist[1][0] > dist[0][0] = 5 + map[1][0] = 3;  => dist[1][0] = 8 add

dist[1][1] > dist[1][0] = 8 + map[1][1] = 9; => dist[1][1] = 17 add

dist[2][0] > dist[1][0] = 8 + map[2][0] = 3; => dist[2][0] = 11 add

dist[0][0] > dist[1][0] = 8 + map[0][0] = 5; => x

dist[0][2] > dist[0][1] = 8 + map[0][2] = 4;  => dist[0][2] = 12 add

dist[0][0] > dist[0][1] = 10 + map[0][0] = 5 => x

dist[1][1] > dist[0][1] = 10 + map[1][1] = 9 => x

dist[2][1] > dist[2][0] = 11 + map[2][1] =2 = dist[2][1] = 13 

이제 좀 이해가 간다

정점을 하나씩 탐색을 하면서 점차 넓혀가는것이다.

모든 이어진 정점을 탐색하므로 최소값이 갱신될수밖에없다

즉 d[1][1] 이란 값이 도출되려면

d[0][0] -> d[0][1]  -> d[1][1]

d[0][0] -> d[1][0]  -> d[1][1]

이 두 과정을 거치게 된다 각각의 배열은 거기까지 가는 최소값을 저정하게 되서 

결국에는 d[1][1]에는 d[1][1]정점까지의 최소값이 저장디는 것!

내일 한번 더해보자~!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class NodeD implements Comparable
{
	int x;
	int y;
	int cost;
	NodeD(int y, int x, int cost){
		this.y = y; 
		this.x = x;
		this.cost = cost; 
	}
	
	@Override
	public int compareTo(NodeD o) {
		return this.cost - o.cost;
	}
}
public class Main_backjoon_4485_젤다 {
	static int[][] map = new int[125][125];
	static int[][] dist = new int[125][125];
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static int N;
	static final int INF = Integer.MAX_VALUE;
	public static void main(String[] args) throws  IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int num = 1;
		while ( true ) { 
			N = Integer.parseInt(br.readLine());
			if( N == 0 ) {
				break;
			}
			map = new int[N][N];
			dist =new int[N][N];
			for( int i = 0; i < N; i++ ) {
				st = new StringTokenizer( br.readLine(), " ");
				int idx = 0;
				while( st.hasMoreTokens() ) {
					map[i][idx] = Integer.parseInt( st.nextToken() );
					dist[i][idx] = INF;
					idx ++;
				}
			}
			int ans = solve();
			
			//System.out.println("Problem "+num+": "+ans);
			
			sb.append("Problem "+num+": "+ans+ "\n");
			num += 1;
			//printMap()
		}
		System.out.println(sb.toString());
	}
	public static int solve() {
		PriorityQueue pq = new PriorityQueue();
		dist[0][0] = map[0][0]; // 첫번쨰 dist 배열 세팅  
		pq.add(new NodeD( 0, 0, map[0][0]) ); //첫번째를 배열에 넣음
		
		while(!pq.isEmpty()) {
			NodeD n = pq.poll();
			int sero = n.y;
			int garo = n.x;
			int cost = n.cost;
			//꺼낼때마다  현재 보다 크다면 무시한다.
			if( dist[sero][garo] < cost) {
				continue;
			}
	
			
			
			for(int i = 0; i < 4;  i++) {
				int yy = dy[i] + sero;
				int xx = dx[i] + garo;
				if ( xx >= 0 && xx < N &&  yy >= 0  && yy < N ) {
					//yy,xx 까지 가는 길이 sero 
					if(dist[yy][xx] > dist[sero][garo] + map[yy][xx]) { //최단거리 세팅 
						dist[yy][xx] = dist[sero][garo] + map[yy][xx];
						pq.add(new NodeD(yy, xx, dist[yy][xx]));
					}
				}	
			}
		}
		return dist[N-1][N-1];
		
	}
	public static void printMap() {
		for(int i = 0 ; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(dist[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	
	
	

}

ㅋㅋㅋ

만약에..만약에 이문제를풀고 최단경로 문제들을 좀 풀었으면..결과가 달랐을 수도 있겠다 싶다.

다익스트라. 참 가까우면서도 먼 문제였다

두줄이 마음에 안와닿아서 꺼려졌었는데

이제는 이해가 간다

계속 틀려서 너무 짜증났는데 알고보니 입출력이 잘못되있었다...허무

일단 우선순위 큐를 사용하기 위해

node를 implement comparable 하고

compareTo 메소드를 이용하여 힙에 세팅한다.

그외에는 위에서 설명한 것과 같다..

예전에 다익스트라 문제를 못풀어서 정말 미쳐버릴것같은 때가 있었다..

코드도 이해가 안되서 한참을 삽질했었는데...

참..ㅋㅋㅋ