BJ16236 아기 상어

https://www.acmicpc.net/problem/16236

NxN 사이즈의 맵과 그 안에 물고기들과 상어의 위치가 주어진다.
상어는 자신보다 작은 물고기만 먹을 수 있고, 상어는 먹은 물고기의 수에 따라 크기가 증가한다.
문제는 상어가 물고기를 먹을 수 있는 시간을 요구한다.

물고기들을 리스트에 담아 관리하고, BFS를 이용해 구현했다.

package day0223;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Shark {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int[][] map;
	static int N, x, y, sharkSize = 2, time = 0, numofEat = 0;
	static int[][] dir = {{1, 0},{0, -1},{0,1},{-1,0}};
	public static class Fish implements Comparable<Fish> {
		int x, y, dist;

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

		@Override
		public int compareTo(Fish o) {
			return this.dist == o.dist ? (this.x == o.x ? (this.y - o.y) : this.x - o.x) : this.dist - o.dist;
		}
	}

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		int tmp;
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				tmp = Integer.parseInt(st.nextToken());
				if (tmp == 9) {
					x = i;
					y = j;
				} else {
					map[i][j] = tmp;
				}
			}
		}
		LinkedList<Fish> q = new LinkedList<Fish>();
		boolean[][] visited = new boolean[N][N];
		visited[x][y] = true;
		q.add(new Fish(x, y, 0));
		while(!q.isEmpty()) {
			Fish cur = q.poll();
			if(map[cur.x][cur.y] != 0 && map[cur.x][cur.y] < sharkSize) {
				numofEat++;
				if(numofEat == sharkSize) {
					sharkSize++;
					numofEat = 0;
				}
				time += cur.dist;
				x = cur.x;
				y = cur.y;
				map[x][y] = 0;
				visited = new boolean[N][N];
				visited[x][y] = true;
				
				q.clear();
				q.add(new Fish(cur.x, cur.y, 0));
				Collections.sort(q);
				continue;
			}
			
			
			for(int d = 0; d < 4; d++) {
				int mX = cur.x + dir[d][0];
				int mY = cur.y + dir[d][1];
				
				
				// 이동할 수 없는 곳 걸러내기.
				if(mX >= N || mX < 0 || mY >= N || mY < 0) {
					continue;
				}else if(visited[mX][mY]) {
					continue;
				}else if(sharkSize < map[mX][mY]) {
					continue;
				}
				
				q.add(new Fish(mX, mY, cur.dist + 1));
				Collections.sort(q);
				visited[mX][mY] = true;
			}			
		}
		
		bw.append(Integer.toString(time));
		bw.flush();

	}
}