[BAEKJOON] 아기상어

---

※ 아기상어가 먹을 수 있는 물고기를 찾는다고 해서 바로 먹으면 금물!

먹을 수 있는 물고기 리스트에 저장해놨다가 가장 위에 있는, 그 다음으로 가장 왼쪽에 있는 물고기 딱 한 마리만 먹을 수 있다는 것을 잊지 말자.

이때 활용한 것이 Comparable 인터페이스이다.

아기상어와 물고기의 거리를 나타낼 dist 필드를 기준으로 정렬해줄 건데, 아래 코드를 보면 거리가 같을 경우, 가장 위쪽(x 좌표가 더 작은)에 있는 물고기로, 물고기 위치를 상하로 따질 수 없는 경우는 최후의 수단으로 가장 왼쪽(y좌표가 더 작은)에 있는 물고기를 선택할 수 있도록 compareTo() 메소드가 정의되어 있다.

 

✅ 반복, 종료조건 파악하기

초기 위치에서 가장 가까이에 있는 위치의 물고기를 찾아나선다(bfs).

가장 가까이에 있는 물고기를 먹고도 아기상어보다 몸집이 작은 물고기가 있다면 물고기를 찾아나선다(bfs).

또 다시 아기 상어의 몸집이 커질 수 있는지 체크해주고, 해당 위치에서 다시 먹을 수 있는 물고기를 찾아 떠난다. (몸집이 불어났으면 아기상어보다 더 큰 물고기를 먹을 수 있는 가능성 때문에 여정을 떠남..)

but, 몸집이 불어났는데도 불구하고, 먹을 수 있는 물고기가 없다면 엄마 상어를 호출한다 == 종료 조건

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

public class Main {
	static int N, arr[][], dir[][] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	static int sharkX, sharkY, sharkSize = 2, timer = 0, eatCnt=0;
	static boolean visit[][];

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		visit = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if (arr[i][j] == 9) {
					sharkX = i;
					sharkY = j;
					arr[i][j] = 0;
				}
			}
		}
		int result = 0;
		while (true) {
			visit = new boolean[N][N];
			result = bfs(sharkX, sharkY);
			if (result == -1)
				break;
			timer += result;
		}
		System.out.println(timer);
	}

	private static int bfs(int x, int y) {
		Queue<Fish> fish = new ArrayDeque();
		ArrayList<Fish> list = new ArrayList();
		fish.add(new Fish(x, y, 0));
		visit[x][y] = true; // 아기상어 초기 위치 방문체크

		while (!fish.isEmpty()) { // 아기상어 초기 위치에서부터 최대한 움직였을 때 물고기 얼마나 먹었는지
			Fish now = fish.poll(); // 현재 위치에서 탐색 시작
			for (int d = 0; d < 4; d++) {
				int nextX = now.x + dir[d][0];
				int nextY = now.y + dir[d][1];
				if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N && !visit[nextX][nextY]
						&& arr[nextX][nextY] <= sharkSize) { // 크기가 아기상어보다 크면 못 지나감
					fish.add(new Fish(nextX, nextY, now.dist + 1)); // 갈 수 있는 위치
					visit[nextX][nextY] = true;
					if (arr[nextX][nextY] != 0 && arr[nextX][nextY] < sharkSize) { // 아기상어보다 작은 물고기 만났을 땐 먹이 리스트 후보에 추가
						list.add(new Fish(nextX, nextY, now.dist + 1));
					}
				}
			}
		}
		// 움직였을 때 먹을 수 있던 물고기 있다면 제일 가까운 물고기 먹기
		if (!list.isEmpty()) {
			Collections.sort(list);
			arr[list.get(0).x][list.get(0).y] = 0;
			eatCnt++;
			sharkX = list.get(0).x;
			sharkY = list.get(0).y; 
			if (eatCnt >= sharkSize) {
				sharkSize++;
				eatCnt = 0; // 물고기 먹고 초기화
			}
			return list.get(0).dist;
		}else {
			return -1;
		}
	}

	private 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) {
			if (o.dist == this.dist) { // 거리가 같으면
				if (o.x == this.x) // x까지 같으면
					return this.y - o.y;
				else
					return this.x - o.x;
			}
			return this.dist - o.dist;
		}
	}
}

[출처]

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

16236번: 아기 상어