[BOJ 16236] 아기상어

문제

• BOJ 16236
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

좌표에 물고기는 가만히 있고 상어가 움직이면서 조건에 따라 상하좌우 움직이면서 물고기를 먹을 수 있는지 판단한다. 1초동안 상어가 갈 수 있는 모든 좌표를 바라보면서 먹을 수 있는 좌표를 만나면 그 좌표를 상어좌표로 바꿔주고 이를 반복한다. 따라서 좌표를 관리할 큐를 생성한다.

1. 먹은 물고기 수 == 상어크기이면 크기가 하나 증가하므로 이를 기록하기 위한 eatCnt, 한번 탐색할때마다 먹을 물고기를 찾았는지를 관리할 isEat변수를 생성한다.
2. while : 상어를 먹을 수 있을 때 까지(isEat==true) 탐색을 시작한다.
   1. 상어가 갈 수 있는 좌표를 관리할 큐 q, 먹을 수 있는 물고기를 관리할 pq, 방문처리를 관리하는 visited배열을 생성하고 초기의 상어좌표 sharkX, sharkY를 q에 넣고 방문처리한다. 상어가 한번 탐색하면서 이동한 거리를 저장할 d를 생성한다.
   2. q가 빌 때 까지 다음을 반복한다.
      1. 이동거리를 하나 증가시키고 현재 큐에 있는 좌표들을 모두 꺼낸다.
         1. 상어가 갈 수 있는 좌표를 하나 꺼내 4방향 탐색으로 다음 좌표 nx, ny를 구한다.
         2. nx, ny 의 범위와 방문여부를 체크하고 이를 만족하면 먹을 수 있는지를 판단한다.
            • 상어의 크기보다 작고 0보다 크다면 먹을 수 있는 물고기이다.
              • pq에 물고기 후보로 넣어준다.
            • 좌표값이 0or9이거나 좌표값이 상어크기랑 같으면 먹을수는 없지만 지나갈 수 있다.
              • 다음 탐색을 위해 q에 넣어준다.
      2. 현재 이동거리에서의 갈 수 있는 모든 경우가 끝난 후 먹을 수 있는 물고기를 아직 못구했으면 다시 q에서 좌표를 꺼내고 찾았으면 탐색을 종료한다.
   3. pq에서 먹을 수 있는 물고기를 하나 고른다.
      1. pq의 타입 Point클래스에서 비교 우선순위를 x가 작으면서 x가 같으면 y가 작은순으로 정렬되어 있으므로 이를 만족하는 물고기가 먼저 pop된다.
      2. eatCnt를 하나 증가시키고 상어크기와 같다면 상어크기를 하나 증가시켜주고 eatCnt를 초기화한다.
      3. 이 물고기를 찾기까지의 이동 거리 d를 최종답인 Ans에 누적합해준다.
   4. pq가 비었다면 더이상 물고기를 먹을 수 없으므로 종료한다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M; // 크기, 물고기 수
	static int[][] dArr = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;
	static PriorityQueue<Point> pq;
	static Queue<Point> q;
	static int sharkX, sharkY; // 상어의 현재 좌표
	static int sharkS = 2; // 상어의 크기
	static boolean[][] visited;
	static int Ans;

	static class Point implements Comparable<Point> {
		int x, y; // 현재좌표

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

		@Override
		public int compareTo(Point o) {
			if (this.x == o.x)
				return Integer.compare(this.y, o.y);
			else
				return Integer.compare(this.x, o.x);
		}
	}

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int size = Integer.parseInt(st.nextToken());
				if (size == 9) { // 상어 세팅
					sharkX = i;
					sharkY = j;
				} else
					map[i][j] = size;
			}
		} // End input

		bfs();
		System.out.println(Ans);
	}

	private static void bfs() {
		int eatCnt = 0; // 먹은 물고기 수가 자신의 크기와 같아지면 초기화
		boolean isEat = true; // 탐색동안 먹었는지 체크

		while (isEat) { // 먹을 수 있는 물고기가 있을 때만 탐색
			pq = new PriorityQueue<>();
			q = new LinkedList<>(); // 현재 상어위치에서 갈 수 있는 경우를 모두 저장
			visited = new boolean[N][N];

			q.add(new Point(sharkX, sharkY));
			visited[sharkX][sharkY] = true;
			int d = 0; //이동거리

			while (!q.isEmpty()) {
				int size = q.size();
				d++;

				// 현재 갈 수 있는 거리에서 먹을 수 있는 물고기 찾기
				for (int s = 0; s < size; s++) {
					Point now = q.poll();

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

						if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
							visited[nx][ny] = true;
							// 먹을 수 있는 물고기면
							if (map[nx][ny] > 0 && sharkS > map[nx][ny])
								pq.add(new Point(nx, ny));
							// 먹을수는 없지만 지나갈 수 있다면
							else if (map[nx][ny] == 0 || map[nx][ny] == sharkS)
								q.add(new Point(nx, ny));
						}
					}
				}
				
				if(pq.size() > 0) break;
			}

			// 먹을 수 있는 물고기를 찾았는지 검사
			if (pq.size() > 0) {
				Point p = pq.poll();
				map[p.x][p.y] = 0; // 먹음
				sharkX = p.x;
				sharkY = p.y;
				
				if (++eatCnt == sharkS) { // 상어의 크기만큼 먹었으면 크기 증가
					sharkS++;
					eatCnt = 0;
				}
				Ans += d; // 이동거리 누적
				isEat = true;
			} else
				isEat = false; // 더이상 먹을 물고기 없으므로 모든 탐색 종료
		}
	}
}