백준 16236 아기 상어 (자바)

import java.io.BufferedReader;
import java.io.FileInputStream;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class algo_16236_김어진 {
	static int[][] dMove = {{-1,0},{0,1},{1,0},{0,-1}};
	static int N;
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		int answer =0;
		int [][] board  = new int[N][N];
		Shark shark=null;
		
		
		//ArrayList<Fish> fish =new ArrayList<>(); 
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine()," ");
			for (int j = 0; j < N; j++) {
				int x=Integer.parseInt(st.nextToken());
				
				if(x==9) shark=new Shark(i,j,2);
				else board[i][j]= x; 
				//else if(x>=1 && x<=6) fish.add(new Fish(i,j,x));
			}
		}
		int eatCount=0;
		while(true) {
			int nowX=shark.x;
			int nowY=shark.y;
			Fish fs = findFish(board,shark);
			if(fs==null) break;
			answer+=fs.move;
			board[fs.x][fs.y]=0;
			shark.x=fs.x;
			shark.y=fs.y;
			eatCount++;
			if(eatCount==shark.size) {
				shark.size++;
				eatCount=0;
			}
		}
		
		System.out.println(answer);
		
	}
	public static Fish findFish(int[][] board, Shark shark) {
		int distance=Integer.MAX_VALUE;
		int x=Integer.MAX_VALUE;
		int y=Integer.MAX_VALUE;
		Queue<Shark> q = new LinkedList<>();
		//int[][] check = new int[N][N];
		boolean[][] check = new boolean[N][N];
		q.add(new Shark (shark.x,shark.y,shark.size,shark.mv));
		check[shark.x][shark.y]=true;
		
		while(!q.isEmpty()) {
			Shark nowShark = q.poll();
			//나보다 작아야 먹을 수 있음
			if(board[nowShark.x][nowShark.y]>=1 && board[nowShark.x][nowShark.y]<nowShark.size) {
				// 거리가 가까우면 바꾸기
				if(distance>nowShark.mv) {
					distance=nowShark.mv;
					x=nowShark.x;
					y=nowShark.y;
				}
				// 거리가 같으면
				else if(distance ==nowShark.mv) {
					// 높은 위치의 물고기 선택
					if(nowShark.x<x) {x=nowShark.x;y=nowShark.y;}
					// 높이가 같으면 왼쪽에 있는 물고기 선택
					else if(nowShark.x==x) {
						if (nowShark.y<y) {x=nowShark.x; y=nowShark.y;}
					}
				}
			}
			for (int i = 0; i < 4; i++) {
				int nx = nowShark.x+dMove[i][0];
				int ny = nowShark.y+dMove[i][1];
				// 작거나 같으면 이동 가능
				if(nx>=0 && nx < N && ny>=0 && ny < N && !check[nx][ny] &&board[nx][ny]<=nowShark.size) {

					// 이동
					q.add(new Shark(nx,ny,nowShark.size,nowShark.mv+1));
					check[nx][ny]=true;
				}
			}
		}
		if( distance==Integer.MAX_VALUE)return null;
		
		return new Fish(x, y,distance);

		
		
	}
	private static int getDistance(int x1, int y1, int x2, int y2) {
		return Math.abs(x1-x2)+Math.abs(y1-y2);
		
	}
}
class Fish{
	
	int x;
	int y;
	int move;
	
	public Fish(int x, int y,int move) {
		super();
		this.x = x;
		this.y = y;
		this.move = move;
		
	}
}
class Shark{
	int x;
	int y;
	int size;
	int mv;
	
	public Shark(int x, int y, int size) {
		super();
		this.x = x;
		this.y = y;
		this.size = size;
	}

	public Shark(int x, int y, int size, int mv) {
		super();
		this.x = x;
		this.y = y;
		this.size = size;
		this.mv = mv;
	}

}