[백준] 16236_아기 상어(java)

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

16236번: 아기 상어

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

 

 

---

# 접근

상어는 1초에 네 방향으로 움직일 수 있고 이때 상하좌우에 먹을 수 있는 물고기가 존재한다면 리스트에 담아 관리하기로 결정함. 

그리고 먹을 수 있는 물고기가 여러 마리 존재한다면 우선순위에 따라 먹을 물고기를 결정해야 하기 때문에 상어의 현 위치에서 가장 가까운 물고기를 계산해야 함. 따라서 BFS를 이용하여 물고기마다의 거리를 저장해두고 거리가 가장 가까운 물고기를 사냥하는 것으로 생각하였음.

 

이 때 문제에서 제시한 조건대로 상어로부터 거리가 같은 물고기가 존재한다면 가장 위, 가장 왼쪽 물고기를 선택해야 하므로 X좌표에 대한 추가적인 비교가 필요하다고 판단함.

 

 

구현에 필요한 자료구조 및 변수들

• x, y 좌표와 dist 즉, 거리를 담을 수 있는 클래스 : Info 클래스
• 먹을 수 있는 물고기에 대한 정보를 담을 수 있는 ArrayList : ArrayList<Info> fishes
• 상어의 이동과 함께 최단거리를 구하기 위해 사용될 Queue
• 상어의 위치와 물고기의 위치 및 크기를 담을 2차원 배열 : int map[][]
• 탐색을 위한 dx배열과 dy배열
• 상어의 현재 위치를 담을 sx, sy
• 상어가 먹은 물고기의 수를 카운팅하기 위한 count, 상어의 사이즈를 저장하기 위한 size
• 엄마 상어를 호출하기까지 걸리는 시간을 담기 위한 time

package BOJ;

import java.io.*;
import java.util.*;

public class BOJ_16236_아기상어 {

	public static int N, time, sx, sy, size, count, map[][];
	public static ArrayList<Info> fishes;
	public static int dx[] = {-1, 1, 0, 0};
	public static int dy[] = {0, 0, -1, 1};

	// 상어 또는 물고기의 위치와 거리를 담을 클래스 
	static class Info { 
		int x, y, dist;

		public Info(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}

	// 맵 범위 체크 메소드
	public static boolean isRange(int x, int y) {
		return x < 0 || x >= N || y < 0 || y >= N;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		size = 2; // 초기 나이 2로 셋팅

		// 입력으로 주어진 값을 받고 상어가 있는 위치 0으로 초기화
		for(int i = 0; i < N; i++) {
			String input1[] = br.readLine().split(" ");
			for(int j = 0; j < N; j++) {
				int num = Integer.parseInt(input1[j]);
				map[i][j] = num;
				if(num == 9) {
					sx = i;
					sy = j;
					map[i][j] = 0;
				}
			}
		}

		while(true) {
			fishes = new ArrayList<Info>(); // 먹을 수 있는 물고기의 정보를 담을 수 있는 ArrayList 생성
			Queue<Info> q = new LinkedList<Info>(); // bfs 수행을 위한 큐 생성
			boolean visited[][] = new boolean[N][N]; // 방문 표시를 하기 위한 boolean 타입의 2차원 배열 생성
			q.offer(new Info(sx, sy, 0)); // 상어의 위치 q에 삽입, 물고기를 먹었으므로 0으로 거리 갱신
			visited[sx][sy] = true; // 방문 표시

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

				for(int d = 0; d < 4; d++) { // 상하좌우 탐색
					int nx = shark.x + dx[d];
					int ny = shark.y + dy[d];

					if(isRange(nx, ny)) continue; // 범위 체크
					if(visited[nx][ny]) continue; // 방문했는지 여부 체크
					// 먹이를 찾은 경우(0보다 크고 상어의 사이즈보다 작은 경우만 먹을 수 있다는 조건)
					if(1 <= map[nx][ny] && map[nx][ny] < size) {
						q.offer(new Info(nx, ny, shark.dist + 1)); // 상어의 위치 갱신
						fishes.add(new Info(nx, ny, shark.dist + 1)); // 먹이 리스트에 삽입
						visited[nx][ny] = true; //방문 표시
					} 

					// 먹을 수는 없지만 지나갈 수 있는 경우(0이거나 상어의 사이즈와 같은 경우 지나갈 수 있다는 조건)
					else if(map[nx][ny] == size || map[nx][ny] == 0) {
						q.offer(new Info(nx, ny, shark.dist + 1)); // 상어 위치 갱신
						visited[nx][ny] = true; // 방문 표시
					}
				} 
			}

			// 사이즈가 0인 경우 먹을 수 있는 물고기가 없는 경우이므로 출력
			if(fishes.size() == 0) {
				System.out.println(time);
				return;
			}

			// 먹을 물고기가 있는 경우
			Info eatingFish = fishes.get(0);
			for(int i = 1; i < fishes.size(); i++){
				if(fishes.get(i).dist < eatingFish.dist) { // 거리가 최소인 물고기로 갱신
					eatingFish = fishes.get(i);
				}

				if(eatingFish.dist == fishes.get(i).dist) { // 거리가 같은 경우 X가 작은 물고기가 우선순위가 되므로 갱신
					if(eatingFish.x > fishes.get(i).x){
						eatingFish = fishes.get(i);
					}   
				}
			}

			time += eatingFish.dist; // 먹을 물고기의 거리를 time에 추가
			count++; // 먹었으므로 카운트 증가
			map[eatingFish.x][eatingFish.y] = 0; // 물고기를 먹은 자리 0으로 갱신

			if(count == size) { // 먹은 물고기의 수와 상어의 사이즈가 같은 경우
				size++; // 상어의 사이즈 1 증가
				count = 0; // 다시 카운트는 0으로 초기화
			}

			sx = eatingFish.x; // 상어의 위치 갱신
			sy = eatingFish.y; // 상어의 위치 갱신
		}
	}
}