[java 백준] 이것이 코딩테스트이다.- 화성탐사 (java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main{
 
    public static int t;
 
    public static int n;
    public static int[][]arr;
    public static int dirX[]={-1,1,0,0};
    public static int dirY[]={0,0,-1,1};
    public static int distance[][];
    public static boolean visit[][];
    public static final int INF=(int)1e9;
 
    public static class Node{
        int x,y,d;
        public Node(int x,int y,int d){
            this.x=x;
            this.y=y;
            this.d=d;
        }
 
    }
 
    public static void dijkstra(int i,int j){
        Queue<Node>queue=new LinkedList<Node>();
        distance[i][j]=arr[i][j];
        queue.offer(new Node(i,j,arr[i][j])); //arr[i][j]넣어야
 
 
        while(!queue.isEmpty()){
            Node node=queue.poll();
 
            for(int s=0;s<4;s++){
                int nx=node.x+dirX[s];
                int ny=node.y+dirY[s];
                if(nx>=0&&nx<n&&ny>=0&&ny<n){
                    if(node.d+arr[nx][ny]<distance[nx][ny]){
                        //원래 distance에 있는 값보다 더 작은 값이 나타났다?!
                        //갱신
                        distance[nx][ny]=node.d+arr[nx][ny];
                        queue.offer(new Node(nx,ny,distance[nx][ny]));
 
                    }
                }
 
            }
 
        }
 
 
    }
 
 
    public static void main(String[]args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        t=Integer.parseInt(br.readLine());
        Queue<Node>queue=new LinkedList<Node>();
        for(int s=0;s<t;s++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n][n];
            distance = new int[n][n];
            visit=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());
                }
            }
 
            //distance를 무한대로
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    distance[i][j]= INF;
                }
            }
 
           
 
            dijkstra(0,0);
            System.out.println(distance[n-1][n-1]);
 
 
 
        }
 
 
 
 
 
    }
}