백준 - 16236번(아기 상어)

문제 출처: https://www.acmicpc.net/problem/16236

문제

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

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

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

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

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

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

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static int[][] directions = {
			{ -1, 0 },	// 상
			{ 1, 0 },	// 하
			{ 0, -1 },	// 좌
			{ 0, 1 },	// 우
	};
	
	private static int sharkSize = 2; 	// 상어 크기
	private static int currentEat = 0; 	// 상어 크기 성장 유무를 판별하기 위한 변수
	private static List<Fish> feedList = new ArrayList<>(); // 먹이를 저장하는 리스트
	private static int result = 0; // 결과값을 저장하기 위한 변수
	
	private static class Fish implements Comparable<Fish> {
		
		int y;
		int x;
		int dist;
		
		public Fish(int y, int x, int dist) {
			this.y = y;
			this.x = x;
			this.dist = dist;
		}

		@Override
		public int compareTo(Fish o) {
			if (this.dist == o.dist) {
				if (this.y == o.y) {
					// 행이 같을 경우 열 기준 오름차순
					return this.x - this.x;
				} else {
					// 거리가 같을 경우 행 기준 오름차순
					return this.y - o.y;
				}
			} else {
				// 거리기준 오름차순
				return this.dist - o.dist;
			}
		}
		
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(reader.readLine()); // 공간의 크기
		
		Fish shark = null;
		
		// 초기 배열 설정
		int[][] fishes = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
			for (int j = 0; j < N; j++) {
				fishes[i][j] = Integer.parseInt(tokenizer.nextToken());
				// 상어 위치 찾기
				if (fishes[i][j] == 9) {
					shark = new Fish(i, j, 0);
					fishes[i][j] = 0;
				}
			}
		}
		
		bfs(fishes, shark, N);
		
		System.out.println(result);
	}
	
	private static void bfs(int[][] fishes, Fish shark, int N) {
		boolean[][] visited = new boolean[N][N];
		Queue<Fish> queue = new ArrayDeque<>();
		queue.offer(shark);
		visited[shark.y][shark.x] = true; // 현재 위치 방문 처리
		
		while (!queue.isEmpty()) {
			Fish current = queue.poll();
			int currentDist = current.dist; // 현재 위치까지 이동한 거리
			
			for (int i = 0; i < 4; i++) {
				int dy = current.y + directions[i][0]; // 행
				int dx = current.x + directions[i][1]; // 열
				
				// 유효 인덱스이고
				if (dy >= 0 && dy < N && dx >= 0 && dx < N) {
					// 아직 탐색하지 않은 곳이고
					if (!visited[dy][dx]) {
						// 상어가 먹을 수 있는 물고기인 경우
						if (fishes[dy][dx] != 0 && fishes[dy][dx] < sharkSize) {
							feedList.add(new Fish(dy, dx, currentDist + 1)); // 먹이 리스트에 추가
							queue.offer(new Fish(dy, dx, currentDist + 1));  // 탐색 큐에 추가
							visited[dy][dx] = true;
						}
						
						// 비어있거나 지나갈수만 있는 물고기인 경우
						if (fishes[dy][dx] == 0 || fishes[dy][dx] == sharkSize) {
							queue.offer(new Fish(dy, dx, currentDist + 1));
							visited[dy][dx] = true;
						}
					}
				}
			}
		}
		
		// 먹을 수 있는 먹이가 있는 경우 - 한번에 하나의 물고기만 먹는다
		if (!feedList.isEmpty()) {
			Collections.sort(feedList); // 먹이 정렬
			
			Fish eatTarget = feedList.get(0); // 가장 우선순위가 높은 물고기 먼저 먹음(가깝고, 가장 위쪽에 가장 왼쪽)
			shark.y = eatTarget.y; // 먹이의 위치로 상어 위치 이동
			shark.x = eatTarget.x;
			fishes[shark.y][shark.x] = 0; // 먹이를 먹은 위치를 빈 곳으로 만듦
			
			if (++currentEat == sharkSize) {
				sharkSize++; // 상어의 크기와 같은 횟수를 먹으면 상어 크기 증가
				currentEat = 0;
			}
			
			result += eatTarget.dist; // dist 변수에 해당 먹이까지의 거리 정보를 가지고 있음
			
			feedList.clear();
		} else return;
		
		bfs(fishes, shark, N);
	}

}

• 적절한 접근법을 찾지 못해 상당히 긴 시간이 소요된 문제였다.
• 주어진 조건에 따라 물고기 정보를 담는 내부 클래스를 선언하고, Comparable을 구현하여 우선순위를 설정하였다.
• 들어온 값들로 배열을 완성하고 처음 상어의 위치를 구해서 상어의 정보를 담는 Fish 객체를 만든 뒤, 상어의 자리를 0으로 바꾸어 이동할 수 있는 위치로 만든다.
• Fish 클래스는 각 물고기의 좌표 정보와 도달하기까지의 거리 정보를 가진다.
• 먹을 수 있는 물고기가 있는 동안 BFS를 반복 수행한다.
• 상어의 정보를 매개변수로 전달하여 그 위치부터 BFS를 수행한다. 먹이를 찾은 경우 먹이 리스트에 추가하고 탐색 큐에 해당 정보를 추가한다.
• 비어있거나 크기가 같아서 지나갈 수만 있는 물고기의 경우, 탐색 큐에 해당 정보를 추가하는 작업만 수행한다.
• 현재의 상황에서 갈 수 있는 모든 물고기들의 위치 탐색을 마친 뒤, 먹이 리스트에 있는 값을 하나 꺼내온다. 이때, 우선순위에 맞게 꺼내와야 하므로 정렬을 하고 제일 앞의 원소를 가져온다.
• 먹이의 위치로 상어 위치를 이동하고, 먹이 위치의 값을 0으로 바꾼다. 상어의 크기와 같은 수의 물고기를 먹으면 상어 크기를 증가시키고, 그 물고기를 먹기까지의 이동 길이를 더한다. 물고기를 다 먹었으면 먹이 리스트를 비워 다음 탐색을 준비하고, 다시 bfs를 수행한다.
• 먹이 리스트가 존재하지 않을 때까지 재귀를 반복한다.