[삼성기출]백준16236 - 아기상어

import java.io.*;
import java.util.*;
public class Main16236_아기상어 {
	
	static int N, res, size = 2, bite;	// 아기상어의 크기 2 초기
	static int[][] dir = {{-1,0},{0,-1},{0,1},{1,0}};
	static int[][] map;
	static boolean check(int x, int y) {
		if(x>=0 && x<map.length && y>=0 && y<map[x].length)
			return true;
		else return false;
	}
	
	static boolean[][] visit;
	static Pos shark;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().trim());
		map = new int[N][N];
		
		String[] str = null;
		for(int i=0; i<N; i++) {
			str = br.readLine().trim().split(" ");
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(str[j]);
				if(map[i][j] == 9) {
					shark = new Pos(i,j);
					map[i][j] = 0;
				}
			}
		}
		
		canBite=true;	// 아기상어가 먹을 물고기가 있는지 체크. 일단 한바퀴 돌기위해 true
		while(canBite) {
			visit = new boolean[N][N];
			play(shark.x, shark.y);		// 물고기 한마리 잡아먹기 Play!
			if(bite == size) {			// 잡아먹은 수가 크기와 같으면 크기+1
				size++;					// 문제의 설명이 부족하지만,
				bite=0;					// 크기가 증가하면 먹은갯수 0으로 초기화 해줘야 함.
			}
		}
		
		System.out.println(res);
	}
	
	
	static boolean canBite;
	static void play(int x, int y) {
		canBite = false;
		Queue<Pos> qu = new LinkedList<>();			// 같은 시간동안 갈 수 있는 곳.
		Queue<Pos> quT = new PriorityQueue<>();		// 갈수있는 곳 중에 조건에 맞는 가장 가까운 물고기.
		int dx, dy, time = 0, s;
		visit[x][y] = true;
 
		qu.add(new Pos(x,y));
		while(!qu.isEmpty()) {
			s = qu.size();
			Pos p = null;
			time++;
			/*
			 * 시간단위로 계산함.
			 */
			for(int i=0; i<s; i++) {
				p = qu.poll();
				for(int d=0; d<4; d++) {
					dx = p.x + dir[d][0];
					dy = p.y + dir[d][1];
					if(check(dx,dy) && !visit[dx][dy] && map[dx][dy] <= size) {
						qu.add(new Pos(dx,dy));
						visit[dx][dy] = true;
					}
				}
			}
			/*
			 * 시간단위로 갈 수 있는 모든곳에서 조건에 맞게 물고기가 있으면 리턴.
			 */
			quT.addAll(qu);
			while(!quT.isEmpty()) {
				p = quT.poll();
				if(map[p.x][p.y]!=0 && map[p.x][p.y]<size) {
					res+=time;
					shark.x = p.x;
					shark.y = p.y;
					map[p.x][p.y] = 0;
					bite++;
					canBite = true;
					return;
				}
			}
		}
	}
	
	static void print() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println(size+"  ============    "+res);
	}
	
	static class Pos implements Comparable<Pos>{
		int x,y;

		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "[" + x + "," + y + "]";
		}
		/*
		* x,y 순으로 정렬합니다.
		*/
		@Override
		public int compareTo(Pos o) {
			if( this.x > o.x) return 1;
			else if( this.x == o.x) {
				return this.y - o.y;
			}
			else return -1;
		}
		
	}
}