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

https://www.acmicpc.net/problem/4485

N개의 테스트 케이스별로 주어지는 M*M Map에서 (0,0) -> (M-1,M-1)까지의 비용을 구하는 문제로, 주어지는 Map이 가중치이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t;
        int count =1;
        StringBuilder sb = new StringBuilder();
        while((t = par(br.readLine()))!=0){
            int[][] map = new int[t][t];
            int[][] dist = new int[t][t];
            for (int i = 0; i < map.length; i++) {
                map[i] = getArray(br.readLine());
                Arrays.fill(dist[i],Integer.MAX_VALUE);
            }
            dist[0][0] = map[0][0];
            boolean[][] visited = new boolean[t][t];
            PriorityQueue<Cave> pq = new PriorityQueue<>(Comparator.comparingInt(c -> c.weight));
            Cave start = new Cave(0,0);
            start.weight = dist[0][0];
            pq.offer(start);
            int ans = -1;
            while(!pq.isEmpty()){
                Cave c = pq.poll();
                int i = c.i;
                int j = c.j;
                int weight = c.weight;
                if(visited[i][j]) continue;
                visited[i][j] = true;
                if(i==t-1&&j==t-1){
                    ans = weight;
                    break;
                }
                for (int k = 0; k < 4; k++) {
                    if(check(i+dx[k], j+dy[k],map,visited)){
                        if(dist[i+dx[k]][j+dy[k]]>weight+map[i+dx[k]][j+dy[k]]){
                            dist[i+dx[k]][j+dy[k]] = weight+map[i+dx[k]][j+dy[k]];
                            Cave target = new Cave(i+dx[k],j+dy[k]);
                            target.weight = dist[i+dx[k]][j+dy[k]];
                            pq.offer(target);
                        }
                    }
                }
            }
            sb.append("Problem ");
            sb.append(count++);
            sb.append(": ");
            sb.append(ans);
            sb.append("\n");
        }sb.delete(sb.length()-1,sb.length());
        System.out.println(sb);
    }

    static boolean check(int i, int j, int[][] map, boolean[][] visited){
        if(i<0||i>=map.length) return false;
        if(j<0||j>=map[0].length) return false;
        if(visited[i][j]) return false;
        return true;
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Cave{
    int i;
    int j;
    int weight;
    Cave(int i, int j){
        this.i = i;
        this.j = j;
    }
}