[BaekJoon] 16236 아기 상어 (Java)

1.  문제 링크

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

2.  문제

요약

• NxN 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있습니다.
• 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수인데, 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동합니다.
• 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지날 수 없고, 자신의 크기보다 작은 물고기만 먹을 수 있습니다.
• 아기 상어와 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지날 수 있습니다.
• 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같습니다.
  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청합니다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 갑니다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 갑니다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값입니다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹습니다.
• 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없습니다.
• 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가합니다.
• 공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 20보다 작거나 같은 공간의 크기 N이 주어지고 두 번째 줄부터 N개의 줄에는 공간의 상태가 주어집니다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 지닙니다.
  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치
• 출력: 첫 번째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력합니다.

3.  소스코드

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, size = 2;
	static int[][] map, time;
	static Point shark;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		map = new int[N][N];
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) {
				map[row][col] = scanner.nextInt();
				if(map[row][col] == 9) {
					map[row][col] = 0;
					shark = new Point(row, col);
				}
			}
		}
	}
	
	static void solution() {
		int eatNum = 0, answer = 0;
		Point fish;
		while(true) {
			fish = bfs(shark);
			if(fish.x != 20 && fish.y != 20) {
				eatNum++;
				answer += time[fish.x][fish.y];
				map[fish.x][fish.y] = 0;
				shark = fish;
				if(eatNum == size) {
					size++;
					eatNum = 0;
				}
			} else break;
 		}
		System.out.println(answer);
	}
	
	static Point bfs(Point curSharkLoc) {
		Queue<Point> sharkLoc = new LinkedList<Point>();
		sharkLoc.offer(curSharkLoc);
		time = new int[N][N];
		int min = Integer.MAX_VALUE;
		Point answer = new Point(20, 20);
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		while(!sharkLoc.isEmpty()) {
			Point loc = sharkLoc.poll();
			for(int index = 0; index < 4; index++) {
				int cx = loc.x + dx[index];
				int cy = loc.y + dy[index];
				if(isInMap(cx, cy) && canMove(cx, cy)) {
					time[cx][cy] = time[loc.x][loc.y] + 1;
					if(time[cx][cy] <= min) {
						if(map[cx][cy] != 0 && map[cx][cy] < size) {
							if(min > time[cx][cy]) {
								min = time[cx][cy];
								answer = new Point(cx, cy);
							} else if(answer.x > cx || ((answer.x == cx) && (answer.y > cy))) {
								answer = new Point(cx, cy);
							}
						}
					}
					sharkLoc.offer(new Point(cx, cy));
				}
			}
		}
		return answer;
	}
	
	static boolean isInMap(int x, int y) {
		if(x >= 0 && x < N && y >= 0 && y < N) return true;
		return false;
	}
	
	static boolean canMove(int x, int y) {
		if(map[x][y] <= size && time[x][y] == 0) return true;
		return false;
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	static class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}