[BFS] 완전탐색하여 최단 비용 구하기 - 자외선 차단하기

import java.util.Scanner;
 
class Info{
    int x;
    int y;
    public Info(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
    
}
public class Main {
    static int[][] matrix, check;
    static int N, M, answer, rear, front;
    static int[][] Queue;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        //M = sc.nextInt();
        matrix = new int[N][N];
        check = new int[N][N];
        Queue = new int[11000][2];
        rear = 0;
        front = 0;
        sc.nextLine();
 
        for(int i=0;i<N;i++){
            String line = sc.nextLine();
            for(int j=0;j<N;j++){
                matrix[i][j] = Integer.parseInt(line.substring(j,j+1));    
                check[i][j]=1000000;
            }
        }
        
        int[] dirX={-1,1,0,0};
        int[] dirY={0,0,1,-1};
        enqueue(0, 0);
        check[0][0] = matrix[0][0];
        
        while(!isEmpty()){
            Info info = dequeue();
            int x = info.x;
            int y = info.y;
            for(int k=0;k<4;k++){
                int nexX = x+dirX[k];
                int nexY = y+dirY[k];                
                 if(nexX<0 || nexX>=N || nexY<0 || nexY>=N) continue;
                 if(check[x][y]+matrix[nexX][nexY]<check[nexX][nexY]){
                     check[nexX][nexY] = check[x][y]+matrix[nexX][nexY];
                     enqueue(nexX, nexY);
                 }
            }
        }
        
        System.out.println(check[N-1][N-1]);
    }
 
    private static boolean isEmpty() {
        return front==rear;
    }
 
    private static void enqueue(int x, int y) {
        rear = (rear+1) % 11000;
        Queue[rear][0]=x;
        Queue[rear][1]=y;
    }
 
    private static Info dequeue() {
        front = (front+1)%11000;
        Info info = new Info(Queue[front][0],Queue[front][1]);
        return info;
    }
}