[백준] 16236번 아기 상어 (bfs, java)

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Fish {
	int x,y;
	

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

	
}

public class Main {
	static int n,sx,sy; // 상어좌표 
	static int[][] map;
	static int[][] dis;// 물고기까지의 거리
	static int xpos[]= {0,0,1,-1};
	static int ypos[]= {1,-1,0,0};
	static ArrayList<Fish> list=new ArrayList<>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		map=new int[n][n];
		dis=new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int val=sc.nextInt();
				if(val==9) {//상어 위치~
					sx=j;
					sy=i;
				}else{
					map[i][j]=val;
				}
				
			}
		}

		int shark=2;
		int time=0;
		int cnt=0; // 물고기 먹은 개수 
		
		
		while(true) {
			int min_dis=Integer.MAX_VALUE; // 가장 가까운 물고기와의 거리
			int fy=Integer.MAX_VALUE;
			int fx=Integer.MAX_VALUE;
			for (int i = 0; i < n; i++) {
				Arrays.fill(dis[i], -1);
			}
			Queue<Fish> q=new LinkedList<Fish>();
			q.add(new Fish(sx,sy)); // 매번 새로운 상어위치로 시작한다.
			dis[sy][sx]=0;
			while(q.size()!=0) {
				
				int y=q.peek().y;
				int x=q.peek().x;
				q.poll();
				for (int i = 0; i < 4; i++) {
					
					int yy=y+ypos[i];
					int xx=x+xpos[i];
					if(xx<0 || yy<0 || xx>=n || yy>=n)continue;
					if(map[yy][xx]>shark || dis[yy][xx]!=-1)continue; //0인 곳은 지나감

					dis[yy][xx]=dis[y][x]+1; // 물고기까지 거리
					//크기가 상어랑 같은 물고기는 지나갈 수는 있어야한다.

					if(map[yy][xx]!=0 && map[yy][xx]<shark) { //잡아먹을 수 있는 물고기 중 가까운 위치 업데이트
						if(min_dis>dis[yy][xx]) {
							min_dis=dis[yy][xx];
							fx=xx;
							fy=yy;//가장 가까운 물고기 위치 업데이트
						}else if(min_dis==dis[yy][xx]) {

							if(fy>y || (fy==y && fx>x)) { //거리가 같으면 위,왼쪽 물고기 우선
								fy=yy;
								fx=xx;
							}

						}
					}

					q.add(new Fish(xx,yy));

				}
			}
			
			if(min_dis==Integer.MAX_VALUE)break; //먹을 수 있는 물고기 없으면 update
			time+=dis[fy][fx];
			cnt++;
			if(cnt==shark) {//크기만큼 물고기 먹으면 상어크기+1해준다.
				shark++;
				cnt=0;
			}
			sy=fy;
			sx=fx;
			map[fy][fx]=0;

		}
		System.out.println(time);

	}
	
}