BOJ 4485

문제
누적 값을 우선 순위 큐로 돌리기
--> 해당 값만을 비교해서 틀림

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 loose;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,-1,0,1};
	static boolean[][] visited;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		int cnt = 0;
		while(N!=0) {
			map = new int[N][N];
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<N;j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			visited = new boolean[N][N];
			dfs();
			System.out.println("Problem "+ ++cnt +": "+loose);
			N = Integer.parseInt(br.readLine());
		}
	}
	private static void dfs() {
		PriorityQueue<int[]> pq = new PriorityQueue<>((int[] a, int[] b)->(Integer.compare(a[2], b[2])));
		pq.add(new int[] {0,0,map[0][0]});
		visited[0][0] = true;
		while(!pq.isEmpty()) {
			int[] cur = pq.poll();
			int x = cur[0];
			int y = cur[1];
			if(x==N-1&&y==N-1) {
				loose = cur[2];
				return;
			}
			for(int d=0;d<4;d++) {
				int nx = x+dx[d];
				int ny = y+dy[d];
				if(check(nx,ny) && !visited[nx][ny]) {
					visited[nx][ny]=true;
					pq.add(new int[] {nx,ny,cur[2]+map[nx][ny]});
				}
			}
		}
	}
	private static boolean check(int r, int c) {
		return -1<r && r<N && -1<c && c<N;
	}

}