[Java] 백준 16236번 아기 상어

아기 상어가 물고기를 먹으로 가는 로직이 있을 때 몇 초동안 걸리는지 찾는 문제입니다.

아기 상어의 크기가 주어지며 그 크기만큼 먹으면 크기가 1늘어납니다.
아기 상어는 자신보다 작은 물고기를 먹을 수 있으며 가까운 곳에 있는 물고기부터 먹습니다.
만약 가까운곳에 있는 물고기가 여러 마리라면 더 위쪽에 있는 물고기를 먹으며, y축이 같다면 더 왼쪽에 있는 물고기를 대상으로 합니다.
같은 크기의 물고기가 있는곳과 아무것도 없는 곳은 지나갈 수 있습니다.

예외가 많이 발생하는 문제입니다
1. 상, 좌, 우, 하 순으로 탐색을 하면 위에 있는 여러마리 물고기를 먹는 규칙을 해결 할 수 있다고 생각하였으나 다음과 같은 예외가 있습니다.
5
0 0 0 0 0
0 0 0 0 0
0 0 9 0 1
0 1 0 0 0
0 0 0 0 0

탐색한 순서를 나타내보았을때 아래와 같습니다.
0 0 0 0 0
0 0 2 0 0
0 3 1 4 0
0 0 5 0 0
0 0 0 0 0

조금 더 탐색을 해보았을 때 오른쪽 1(11)을 먼저 탐색해야하지만 왼쪽 아래의 1(10)을 먼저 탐색하게 됩니다.
0 0  6  0  0
0 7  2  8  0
9 3  1  4 11
0 10 5 12 0
0  0  0 13 0

그래서 큐에 들어가있는 값들에 거리가 짧으면서 가장 위쪽과 왼쪽에 가까운 것을 탐색하는 코드를 추가해주었습니다.

2. 루프에서 빠져나가지 못하는경우
3. 시간초과가 나는 경우
4. 처음 상어가 있던 자리를 9에서 0으로 변경해주지 않은 경우

등 다양한 예외에 대한 처리를 생각해보아야 합니다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		Queue<Integer> qy = new LinkedList<Integer>();
		Queue<Integer> qx = new LinkedList<Integer>();
		Queue<Integer> qd = new LinkedList<Integer>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] map = new int[n][n];
			int[][] test = new int[n][n];
			int cnt = 1;
		boolean[][] visit = new boolean[n][n];
		int y = 0;
		int x = 0;
		int d = 0;
		int[] dy = {-1, 0, 1, 0};
		int[] dx = {0, -1, 0, 1};
		int level = 2;
		int eat = 1;
		int nextLevel = 2;
		int ans = 0;
		int findD = 987654321;
		int findY = 987654321;
		int findX = 987654321;
		boolean chk = false;
		for(int i=0; i<n; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 9) {
					map[i][j] = 0;
					y = i;
					x = j;
				}
			}
		}
		qy.add(y);
		qx.add(x);
		qd.add(0);
		while(!qy.isEmpty()) {
			int nextY, nextX;
			y = qy.poll();
			x = qx.poll();
			d = qd.poll();
			visit[y][x] = true;
			for(int i=0; i<4; ++i) {
				nextY = y + dy[i];
				nextX = x + dx[i];
				if(nextY < 0 || nextX < 0 || nextY >= n || nextX >= n || visit[nextY][nextX]) {
					continue;
				}
				if(map[nextY][nextX] == level || map[nextY][nextX] == 0) {
					if(!chk) {
						qy.add(nextY);
						qx.add(nextX);
						qd.add(d + 1);
						visit[nextY][nextX] = true;
					}
				} else if(map[nextY][nextX] <= eat){
					chk = true;
					if(findD > d) {
						findD = d;
						findY = nextY;
						findX = nextX;
					} else if(findD == d) {
						if(findY > nextY) {
							findD = d;
							findY = nextY;
							findX = nextX;
						}
						if(findY == nextY && findX > nextX) {
							findD = d;
							findY = nextY;
							findX = nextX;
						}
					}
				}
			}
			if(chk && qy.isEmpty()) {
				map[findY][findX] = 0;
				test[findY][findX] = cnt++;
				--nextLevel;
				if(nextLevel == 0) {
					++level;
					++eat;
					nextLevel = level;
				}
				ans += findD + 1;
				qy.add(findY);
				qx.add(findX);
				qd.add(0);
				chk = false;
				findD = 987654321;
				findY = 987654321;
				findX = 987654321;
				for(int j=0; j<n; ++j) {
					for(int k=0; k<n; ++k) {
						visit[j][k] = false;
					}
				}
			}
		}
		System.out.println(ans);
	}
}