[백준 16236] 아기상어 <Java>

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Fish{
	int x;
	int y;
	int d;
	Fish(int x, int y, int d) {
		this.x = x;
		this.y = y;
		this.d = d;
	}
}


public class 아기상어 {
	static int map[][];
	static int n,distance,eat,size=2;
	static int dr[] = {-1,0,0,1};
	static int dc[] = {0,-1,1,0};
	static boolean visited[][];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		map = new int[n][n];
		visited = new boolean[n][n];
		
		Queue<Fish> q = new PriorityQueue<>((o1, o2) -> {
			if (o1.d == o2.d) {//같은거리
				if (o1.x == o2.x) return Integer.compare(o1.y, o2.y);//왼쪽부터
				return Integer.compare(o1.x, o2.x);//위부터
			}
			return Integer.compare(o1.d, o2.d);
		});

		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] == 9) {
					q.add(new Fish(i,j,0));//아기상어 큐에 넣기
					visited[i][j] = true;
					map[i][j]=0;
				}
			}
		}
		
		while(!q.isEmpty()) {
			Fish fish = q.poll();
			
			for(int d=0;d<4;d++) {
				int nr = fish.x+dr[d];
				int nc = fish.y+dc[d];
				
				if(!(nr<n && nc<n && nr>=0 && nc>=0)) continue;
				if(visited[nr][nc]) continue;//방문했으니까 던지기
				visited[nr][nc] = true;
				
				if(map[nr][nc] <= size) {
					q.add(new Fish(nr,nc,fish.d+1));
				}
				
			}
			
			if (!q.isEmpty()) {
                Fish f = q.peek();
                if (map[f.x][f.y] < size && map[f.x][f.y] > 0) {
                
                    eat++;
                    if (eat == size) {//자기크기와 같은 수 먹으면 커진다
                        size++;
                        eat = 0;
                    }
                    map[f.x][f.y] = 0;
                    
                    //처음부터 다시시작
                    q.clear();
                    //새로운위치로 가져다 놓기
                    q.add(new Fish(f.x, f.y, 0));
                    distance += f.d;
                    visited = new boolean[n][n];
                    visited[f.x][f.y] = true;
                }
            }
			
		}
		
		System.out.println(distance);
	
	}
	
	
}