백준 16236 : 아기 상어

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

16236번: 아기 상어

[ 문제풀이 ]

상어 시리즈 첫 번째 문제 아기 상어이다. 주어진 조건대로 구현하면 된다.

경우의 수가 여러 개인 시뮬레이션이 아닌 하나의 상어를 계속 움직이는 것이기 때문에 구현에 크게 어려움이 없을 것이다.

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

public class Main {
	
	static int N, answer, fishCnt;
	static int[][] map;
	static boolean[][] visit;
	static Shark babyShark;
	static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
	
	static class Shark {
		int y, x, size, eat, time;

		public Shark(int y, int x, int size, int eat, int time) {
			this.y = y;
			this.x = x;
			this.size = size;
			this.eat = eat;
			this.time = time;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visit = new boolean[N][N];
		
		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) {
					babyShark = new Shark(i, j, 2, 0, 0);
				} else if (map[i][j] > 0) {
					fishCnt++;
				}
			}
		}

		while (true) {
			//더 이상 남은 물고기가 없으면
			if (fishCnt == 0) {
				bw.write(answer + "\n");
				break;
			}
			//먹을 수 있는 물고기가 존재하는지 탐색
			babyShark = findFish();
			//먹을 수 있는 물고기를 찾지 못했다면
			if (babyShark == null) {
				bw.write(answer + "\n");
				break;
			}
		}
		bw.flush(); bw.close(); br.close();
	}

	public static Shark findFish() {
		for (int i = 0; i < N; ++i) {
			Arrays.fill(visit[i], false);
		}
		
		Queue<Shark> q = new LinkedList<>();
		Shark newBabyShark = null;
		boolean fishFind = false;
		visit[babyShark.y][babyShark.x] = true;
		q.offer(babyShark);

		while (!q.isEmpty()) {
			Shark shark = q.poll();

			//먹을 수 있는 물고기가 2마리 이상이면
			if (fishFind) {
				if (shark.time > newBabyShark.time) continue;
				if (map[shark.y][shark.x] >= shark.size || map[shark.y][shark.x] == 0) continue;
				
				if (shark.y < newBabyShark.y) {
					newBabyShark = shark;
				} else if (shark.y == newBabyShark.y) {
					if (shark.x < newBabyShark.x) {
						newBabyShark = shark;
					}
				}
				continue;
			}

			//먹을 수 있는 물고기를 처음 찾음
			if (map[shark.y][shark.x] < shark.size && map[shark.y][shark.x] > 0 && map[shark.y][shark.x] < 7) {
				fishFind = true;
				newBabyShark = shark;
				continue;
			}

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

				if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
				if (visit[ny][nx] || map[ny][nx] > shark.size) continue;

				visit[ny][nx] = true;
				q.offer(new Shark(ny, nx, shark.size, shark.eat, shark.time + 1));
			}
		}

        //먹을 수 있는 물고기가 없음
		if (!fishFind) {
			return null;
		}

		answer = newBabyShark.time;
		fishCnt--;
		
		map[newBabyShark.y][newBabyShark.x] = 9;
		map[babyShark.y][babyShark.x] = 0;

		//먹은 물고기 양이 현재 자신의 몸 크기와 같다면
		if (++newBabyShark.eat == newBabyShark.size) {
			newBabyShark.eat = 0;
			newBabyShark.size++;
		}
		
		return newBabyShark;
	}
}