녹색 옷 입은 애가 젤다지? - 4485번

---

package com.company;

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        int N = 0;
        int T = 1;

        while ((N = Integer.parseInt(br.readLine())) != 0) {
            int[][] arr = new int[N][N];
            boolean[][] visited = new boolean[N][N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
            pq.add(new int[]{0, 0, arr[0][0]});
            visited[0][0] = true;

            while (!pq.isEmpty()) {
                int[] node = pq.poll();

                if (node[0] == N - 1 && node[1] == N - 1) {
                    sb.append("Problem ").append(T++).append(": ").append(node[2]).append("\n");
                }

                for (int i = 0; i < 4; i++) {
                    int nextX = node[0] + d[i][0];
                    int nextY = node[1] + d[i][1];

                    if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N && !visited[nextX][nextY]) {
                        visited[nextX][nextY] = true;
                        pq.add(new int[]{nextX, nextY, node[2] + arr[nextX][nextY]});
                    }
                }
            }
        }

        System.out.println(sb);
    }
}