[알고리즘] 백준4485 - 녹색 옷 입은 애가 젤다지? java풀이

 

처음에 DP 누적합 처럼 풀으려고 착각함.

시간초과 안나게 풀려면 다익스트라만 가능한듯

 

 

package a0401;

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

/*
 dp인줄 알았는데 다익스트라로 해야됨 
 
 */

public class 백준4485녹색옷젤다 {
	
	static int[][] arr;
	static int[][] sumarr;
	static int size;
	
	static class node implements Comparable<node>{
		int xidx;
		int yidx;
		int weight;
		
		node(int xidx, int yidx, int weight){
			this.xidx = xidx;
			this.yidx = yidx;
			this.weight = weight;
		}

		@Override
		public int compareTo(node o) {
			return this.weight-o.weight;
		}
	}
	
	static boolean check(int i, int j) {
		if(0<=i&&i<size && 0<=j&&j<size)return true;
		return false;
	}
	
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int idx = 1;
		while(true) {
			size = Integer.parseInt(br.readLine());
			if(size==0)break;
			
			arr = new int[size][size];
			sumarr = new int[size][size];
			
			for(int i=0; i<size; i++) {
				StringTokenizer ST = new StringTokenizer(br.readLine());
				for(int j=0; j<size; j++) {
					arr[i][j] = Integer.parseInt(ST.nextToken());
					sumarr[i][j] = Integer.MAX_VALUE;
				}
			}
			
			sumarr[0][0] = arr[0][0];
			int result = daic();
			
			sb.append("Problem " + idx + ": " +result+"\n");
			idx++;
		}
		System.out.println(sb.toString());
	}

	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	
	static int daic() {
		PriorityQueue<node> pq = new PriorityQueue<>();
		pq.offer(new node(0,0,arr[0][0]));
		
		while(!pq.isEmpty()) {
			node now = pq.poll();
			int nowi = now.xidx;
			int nowj = now.yidx;
			
			for(int d=0; d<4; d++) {
				int ni = nowi+di[d];
				int nj = nowj+dj[d];
				
				if(check(ni,nj)) {
					if(sumarr[ni][nj] > sumarr[nowi][nowj]+arr[ni][nj]) {
						sumarr[ni][nj] = sumarr[nowi][nowj]+arr[ni][nj];
						pq.offer(new node(ni, nj, sumarr[ni][nj]));
					}
				}
			} 
		}
		return sumarr[size-1][size-1];
	}
	
}