[백준] 16236 아기 상어 [자바]

 

---

https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-16236-%EC%95%84%EA%B8%B0-%EC%83%81%EC%96%B4

백준 16236 아기 상어

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
class Point {
	int x;
	int y;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
	static int N, s_x, s_y;
	static int[][] xy;
	static int[][] cnt;
	static int[] x_move = {-1,1,0,0};
	static int[] y_move = {0,0,-1,1};
	static int shark = 2;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		N = Integer.parseInt(br.readLine());
 		xy = new int[N][N];
 		for(int i = 0; i < N; i++) {
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			for(int j = 0; j < N; j++) {
 				int a = Integer.parseInt(st.nextToken());
 				xy[i][j] = a;
 				if(a == 9) {
 					s_x = i;
 					s_y = j;
 					xy[i][j] = 0;
 				}
 			}
 		}
 		int result = 0;
 		int feed = 0;
 		while(true) {
 			cnt = new int[N][N];
 			int start = s_x;
 			int end = s_y;
 			int time = bfs(s_x, s_y);
 			if(start != s_x || end != s_y) { //시작점이 바뀌었다면 물고기를 먹은 것
 				result += time;
 				feed++; //먹이를 먹음
 				if(shark == feed) { //크기만큼 먹이를 먹었으면
 					shark++;
 					feed = 0;
 				}
 			}
 			else if(s_x == start && s_y == end) { //먹을 수 있는 물고기가 없음
 				break;
 			}
 		}
 		System.out.println(result);
 	}
 	static int bfs(int sx, int sy) {
 		LinkedList<Point> que = new LinkedList<>();
 		que.add(new Point(sx, sy));
 		int min_dist = 401;
 		int min_x = 21;
 		int min_y = 21;
 		while(!que.isEmpty()) {
 			Point point = que.poll();
 			for(int i = 0; i < 4; i++) {
 				int tx = point.x + x_move[i];
 				int ty = point.y + y_move[i];
 				if(tx >= 0 && tx < N && ty >= 0 && ty < N && xy[tx][ty] <= shark) {
 					if(cnt[tx][ty] == 0 || cnt[tx][ty] > cnt[point.x][point.y] + 1) { //tx ty 좌표까지 오는 시간이 기존의 시간보다 짧다면
 						cnt[tx][ty] = cnt[point.x][point.y] + 1;
 						que.add(new Point(tx, ty));
 						if(xy[tx][ty] != 0 && xy[tx][ty] < shark) { //먹을 수 있는 물고기가 있으면
 							if(min_dist > cnt[tx][ty]) { //기존의 최소 거리보다 더 짧은 거리의 물고기가 있다면
 								min_dist = cnt[tx][ty];
 								min_x = tx;
 								min_y = ty;
 							}
 							else if(min_dist == cnt[tx][ty]) {
 								if(min_x > tx) { //거리가 가까운 물고기가 많다면 가장 위에 있는 물고기
 									min_x = tx;
 									min_y = ty;
 								}
 								else if(min_x == tx) { //그러한 물고기가 여러마리라면 
 									if(min_y > ty) {
 										min_x = tx;
 										min_y = ty;
 									}
 								}
 							}
 						}
 					}
 				}
 			}
 		}
 		//먹을 물고기를 찾았으면 물고기를 없얘고 물고기가 있는 좌표를 시작점으로 다시 탐색해야함
 		if(min_x == 21 || min_y == 21) {
 			return 0;
 		}
 		xy[min_x][min_y] = 0;
 		s_x = min_x;
 		s_y = min_y;
 		return min_dist;
  	}
}