[25.03.26] 아기상어

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

//bfs로 방문하면서 먹을 수 있는 물고기 찾음
// 찾으면 거리 반환
// 반환받아서 총 answer에 더함
// 못찾으면 정답 출력
// while (찾을수 있냐?) 보단 while(true)  하고 함수 결과가 찾을수 없다는 결과일때 break 하는게 더 효율적임
// + 이차원 배열 좌표를 int[]로 하기 보다는 그냥 Node 로 객체 만들어서 하는게 정배임

// The main method must be in a class named "Main".
class Main {
    static int N;
    static int[][] map;
    static Node start;
    static int shark=2;
    static int ans=0;
    static int remain=0;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int i=0; i<N; i++){
            String[] s= br.readLine().split(" ");
            for(int j=0; j<N; j++){
                map[i][j]=Integer.parseInt(s[j]);
                if(map[i][j]==9){
                    map[i][j]=0;
                    start = new Node(j,i,0);
                }
            }
        }
        while(true){
            int dist = bfs(start);
            if(dist==-1){
                break;
            }
            ans += dist;
            remain++;
            if(remain==shark){
                shark++;
                remain=0;
            }
        }
        System.out.printf("%d",ans);
        
    }
    public static int bfs(Node start){
        //여기서 초기화
        boolean[][] visited = new boolean[N][N];
        visited[start.y][start.x]=true;
        PriorityQueue<Node> pq = new PriorityQueue<Node>(new Comparator<Node>(){
            @Override
            public int compare(Node o1 , Node o2){
                if(o1.dist==o2.dist && o1.y==o2.y){
                    return o1.x-o2.x;
                }
                else if(o1.dist==o2.dist){
                    return o1.y-o2.y;
                }
                else{
                    return o1.dist-o2.dist;
                }
            }
        });
        pq.add(start);
        while(!pq.isEmpty()){
            Node now = pq.poll();
            //먹이 먹을 수 있을때
            if(map[now.y][now.x]>0 && map[now.y][now.x]<shark){
                map[now.y][now.x]=0;
                start.x = now.x ;
                start.y=now.y;
                return now.dist;
            }
            for(int i=0; i<4; i++){
                int nX = now.x + dx[i];
                int nY = now.y + dy[i];
                if(nX>=0 && nX<N && nY>=0 && nY<N){
                    if(!visited[nY][nX] && map[nY][nX]<=shark){
                        pq.add(new Node(nX,nY,now.dist+1));
                        visited[nY][nX]=true;
                    }
                }
            }
        }
        return -1;
    }
        

    public static class Node{
        int x;
        int y;
        int dist;
        public Node(int x,int y , int dist){
            this.x=x;
            this.y=y;
            this.dist=dist;
        }
    }
}

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