[16236] 아기 상어

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

16236번: 아기 상어

---

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

// 16236 아기 상어
class Main {

	static int N, TIME;
	static int[][] map;
	static Shark s;
	static Queue<Pair> queue;
	static boolean[][] visited;
	static ArrayList<Fish> list;
	static int[][] dir = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N][N];

		TIME = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
				if (map[i][j] == 9) {
					s = new Shark(i, j, 2, 0);
				}
			}
		}

		while (check()) {
			queue = new LinkedList<Pair>();
			visited = new boolean[N][N];
			list = new ArrayList<Fish>();
			int t = TIME;
			BFS(s.row, s.col);

			// *******중요******** list가 비었으면 그 BFS 실행하기 전의 시간이 정답이다.
			if(list.isEmpty()) {
				System.out.println(t);
				return;
			}
			
			// 먹을 물고기가 한개가 아니라면
			if(list.size() != 1) Collections.sort(list);
				
			Fish fish = list.get(0);
			map[s.row][s.col] = 0;
			s.row = fish.x;
			s.col = fish.y;
			s.eat++;
			if(s.eat == s.size) {
				s.size++;
				s.eat=0;
			}
			map[fish.x][fish.y] = 9;
		}

		System.out.println(TIME);
	}

	public static void BFS(int x, int y) {

		queue.add(new Pair(x, y));

		while (!queue.isEmpty()) {

			int len = queue.size();

			TIME++;

			for (int i = 0; i < len; i++) {

				Pair p = queue.poll();
				visited[p.x][p.y] = true;

				for (int j = 0; j < 4; j++) {
					int nx = p.x + dir[j][0];
					int ny = p.y + dir[j][1];

					if (isInside(nx, ny) && !visited[nx][ny] && map[nx][ny] <= s.size) {
						if (map[nx][ny] != 0 && map[nx][ny] < s.size) list.add(new Fish(nx, ny, map[nx][ny]));
						visited[nx][ny] = true;
						queue.offer(new Pair(nx, ny));
					}
				}
			}

			if (!list.isEmpty()) return;
		}
	}

	// 공간에 아기상어가 먹을 수 있는 물고기가 있는지 없는지 확인하는 함수
	public static boolean check() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0 && map[i][j] < s.size && map[i][j] != 9) {
					return true;
				}
			}
		}
		return false;
	}

	public static boolean isInside(int x, int y) {
		if (x >= 0 && x < N && y >= 0 && y < N)
			return true;
		else
			return false;
	}
}

class Shark {
	int row;
	int col;
	int size;
	int eat;

	Shark(int row, int col, int size, int eat) {
		this.row = row;
		this.col = col;
		this.size = size;
		this.eat = eat;
	}
}

class Pair {
	int x;
	int y;

	Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

class Fish implements Comparable<Fish> {
	int x;
	int y;
	int size;

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

	@Override
	public int compareTo(Fish f) {
		if (this.x > f.x) return 1;
		else if (this.x == f.x) {
			if (this.y > f.y)
				return 1;
		}

		return -1;
	}
}

---

[ 문제 풀이 ]

1. check() 함수는 아기상어가 먹을 수 있는 물고기가 있는지 없는지 확인하는 함수인데, true 이면 먹을 수 있는 것이고, false 이면 먹을 수 없는 상태입니다. 이 함수를 이용하여 while() 문의 조건으로 넣었습니다.

2. 먼저 아기상어가 있는 자리에서 BFS 를 수행합니다. BFS를 하면 조건에 맞는 먹을 수 있는 물고기를 Arraylist list에 넣습니다. 그래서 만약에 먹을 수 있는 물고기가 있으면 BFS를 종료합니다.

3. 여기에서 중요한점은 BFS해서 먹을 수 있는 물고기를 list에 넣었는데, list가 비어있다면 먹을 수 있는 물고기가 없기 때문에 그 때의 시간을 출력하고 종료해야 한다는 것입니다.

4. 그리고 list에 먹을 수 있는 물고기가 1마리가 아니고 2마리 이상이면 list를 정렬해줘서 우선순위에 맞는 물고기를 list 제일 앞에 가져옵니다. (우선순위 : 거리가 가장 가까운 물고기들만 list에 들어가 있기 때문에 가장 위에(x좌표가 가장작은) 그런 물고기가 여러마리라면 가장 왼쪽에있는(y좌표가 가장작은) 물고기를 먹습니다.)

5. list의 첫 번째 있는 물고기를 없애고, 그 자리의 좌표를 아기상어 좌표로 저장합니다. 그리고 아기상어의 크기를 증가시키고, 아기상어의 자리라고 표시해줍니다.