[알고리즘] 백준16236 - 아기상어 java

package a0223;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 백준_아기상어16236 {

	static ArrayList<ArrayList<Integer>> fish;
	static int starti;
	static int startj;
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	static int[][] visit;
	static int size;
	static int[][] arr ;
	static int nowsize = 2;
	static int noweatcnt = 0;
	static int sharki;
	static int sharkj;
	static int time;
	
	static boolean check(int i, int j) {
		if(0<=i&&i<size && 0<=j&&j<size)return true;
		return false;
	}
	
	static int fishfind(int i, int j) {
		
		fish = new ArrayList<>();
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {i,j,0});
		
		int flag = 0;
		int fishnum = 0;
		int stdlen = Integer.MAX_VALUE;
		
		while(!q.isEmpty()) {
			int[] tmp = q.poll();
			int nowi = tmp[0]; int nowj = tmp[1];
			int nowlen = tmp[2];
			//System.out.println(Arrays.toString(tmp));
			//System.out.println("후보");
			if(nowlen >stdlen)break;
			for(int d=0; d<4; d++) {
				int ni = nowi+di[d];
				int nj = nowj+dj[d];
				
				//if(nowlen > stdlen)break;
				if(check(ni, nj) && visit[ni][nj]==0 && arr[ni][nj]<=nowsize) {
					visit[ni][nj] = 1;
					//System.out.println("ni:"+ni+" nj:"+nj+" nowlen:"+nowlen);
					q.add(new int[] {ni,nj,nowlen+1});
					
					
					if(1<=arr[ni][nj] && arr[ni][nj]<nowsize && nowlen<=stdlen) {
						fish.add(new ArrayList<Integer>());
						fish.get(fishnum).add(ni);
						fish.get(fishnum).add(nj);
						fish.get(fishnum).add(nowlen+1);
						stdlen = nowlen;
						fishnum++;
					}
				}
			}
			//if(flag == 1)break;
		}
//		System.out.print("fish 후보들: ");
//		System.out.println(fish);
		
		
		return fish.size(); 
	}
	
	static void eat(int i, int j, int nowlen) {
		//time+=(Math.abs(sharki-i)+Math.abs(sharkj-j));	//이동한 거리만큼 시간 증가
		time+=nowlen;
		noweatcnt++;
		
		if(noweatcnt==nowsize) {		//먹은양이 자신의 크기와 같으면 크기 증가
			nowsize++;
			noweatcnt = 0;
		}
		arr[sharki][sharkj] = 0;		//원래있던 자리는 0으로
		sharki = i; sharkj = j;			//상어의 위치 이동 
		arr[sharki][sharkj] = 9;		//먹은곳으로 이동처리
		
		//System.out.println("eat!!: "+" i:"+i+" j:"+j+" 지금시간:"+time+" 상어위치:"+sharki+" "+sharkj);
//		System.out.println("time:"+time+" 상어위치:"+sharki+" "+sharkj+" 상어사이즈:"+nowsize+" 먹은개수:"+noweatcnt);
//		for(int[] t: arr)System.out.println(Arrays.toString(t));
//		System.out.println();
	}
	
	static void arrange() {
		//System.out.println(fish);
		Collections.sort(fish, (ArrayList<Integer> o1, ArrayList<Integer>o2)->{
			if(o1.get(0)==o2.get(0))return o1.get(1)-o2.get(1);
			return o1.get(0) - o2.get(0);
		});
//		System.out.print("정렬후: ");
//		System.out.println(fish);
	}
	
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		size = Integer.parseInt(br.readLine());
		arr = new int[size][size];
		
		for(int i=0; i<size; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<size; j++) {
				arr[i][j] = st.nextToken().charAt(0)-'0';
				if(arr[i][j]==9) {
					starti=i; startj=j;
				}
			}
		}
		
		sharki = starti;
		sharkj = startj;
		
		
		
		while(true) {
			visit = new int[size][size];
			visit[sharki][sharkj] = 1;
			int fishsize = fishfind(sharki, sharkj);
			
			if(fishsize==1) {
				eat(fish.get(0).get(0), fish.get(0).get(1), fish.get(0).get(2));
				//.out.println("Eat!!"+fish.get(0).get(0)+" "+fish.get(0).get(1));
			}else if(fishsize==0) {
				System.out.println(time);
				break;
			}else {
				arrange();
				eat(fish.get(0).get(0), fish.get(0).get(1), fish.get(0).get(2));
			}
		}
		
	}

}