[백준] 16236 : 아기상어

문제

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

 

 

 

입출력

3
0 0 0
0 0 0
0 9 0

 

0

---

아이디어

bfs 

다음 fish 위치 후보 찾기 >> 위치 찾기 >> 물고기 먹음 

 

 

 

코드 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	static int N; // 공간의 크기
	static int[][] box;
	static int EMPTY = 0;
	static int bx, by; // 아기 상어 위치
	static int[][] way = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
	static int fishCnt = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		box = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				if (box[i][j] == 9) {
					bx = i;
					by = j;
					box[i][j] = EMPTY;
				} else if (box[i][j] >= 1 && box[i][j] <= 6) {
					fishCnt += 1;
				}
			}
		}
		// System.out.println("FISH" + fishCnt);
		// 먹을 수 있는 물고기 1마리 >> 먹으러 가기
		// 먹을 수 없는 물고기 1마리보다 많다 >> 거리가 가장 가까운 물고기 먹으러 간다
		// 더 이상 먹을 수 있는 물고기가 공간에 없음 >> 도움 요청
		if (fishCnt == 0) {
			System.out.println(0);
			return;
		}

		int size = 2;
		int eat = 0;
		int time = 0;

		while (true) {
			int[] info = findNextFish(bx, by, size, eat, time);
			if (info[0] == -1 && info[1] == -1) {
				System.out.println(info[4]);
				break;
			}
			bx = info[0];
			by = info[1];
			size = info[2];
			eat = info[3];
			time = info[4];
		}
	}

	static int[] findNextFish(int x, int y, int size, int eat, int time) {
		PriorityQueue<int[]> nextFish = new PriorityQueue<>(Comparator.comparing((int[] a) -> a[2])
				.thenComparing((int[] a) -> a[0]).thenComparing((int[] a) -> a[1]));

		boolean[][] minDist = new boolean[N][N];

		Queue<int[]> queue = new ArrayDeque<>(); //
		queue.add(new int[] { x, y, 0 });// 위치, 거리
		minDist[x][y] = true;

		while (!queue.isEmpty()) {
			int[] now = queue.poll();

			for (int w = 0; w < 4; w++) {
				int nx = way[w][0] + now[0];
				int ny = way[w][1] + now[1];
				if (!inRange(nx, ny))
					continue;
				if (minDist[nx][ny]) // 거리 더 멀면 ㄴㄴ
					continue;
				if (box[nx][ny] == EMPTY || box[nx][ny] <= size) {
					if (box[nx][ny] < size && box[nx][ny] >= 1) {
						nextFish.add(new int[] { nx, ny, now[2] + 1 });
					}
					minDist[nx][ny] = true;
					queue.add(new int[] { nx, ny, now[2] + 1 });

				}
			}
		}
		if (nextFish.isEmpty()) {
			return new int[] { -1, -1, size, eat, time };
		}
		// 실제로 물고기 먹는 작업
		int[] fish = nextFish.poll();
		int nx = fish[0], ny = fish[1], move = fish[2];
		box[nx][ny] = EMPTY; // 좌표에서도 없애야 하고
		fishCnt -= 1; // 물고기 먹었는지 표기도 해야 함
		eat += 1;
		if (eat == size) {
			size += 1;
			eat = 0;
		}
		return new int[] { nx, ny, size, eat, time + move };

	}

	static boolean inRange(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < N;
	}

}