[Java] BOJ16236, 백준 - 아기 상어

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

16236번: 아기 상어

 

시뮬레이션 + BFS 문제이다.

BFS에 익숙하다면 시간 단위로 거리가 가장 가까운 물고기를 찾는 것은 쉽게 해결할 수 있을 것이다.
다만 문제에서 한 가지 골치아팠던 점은 거리가 똑같은 물고기가 여러 마리인 경우에 위쪽에 있는>오른쪽에 있는 물고기 순으로 먹어야한다는 것이다.

그래서 해당 시간에서 먹을 수 있는 물고기가 있다면 pq에 담아주었다.

// 움직일 수 있으면 일단 큐에 담는다.
if (checkIdx(ni, nj) && !visit[ni][nj] && map[ni][nj] <= level) {
	visit[ni][nj] = true;

	// 먹을 수 있는곳은 pq에 담는다
	if (map[ni][nj] < level && map[ni][nj] != 0)
		pq.offer(new Point(ni, nj));
	q.offer(new Point(ni, nj));
}

 

그래서 물고기들의 좌표로 정렬을 어떻게 할까 고민하다가 물고기의 좌표를 저장해줄 Point 객체에 Comparable을 구현하여 사용하기로 했다. 그러면 PriorityQueue를 이용해 담아줄 때 이 순서대로 담긴다.
위쪽/오른쪽 순으로 정렬하려면 i,j 둘 다 역순으로 정렬해줘야했다. 

	static class Point implements Comparable<Point> {
		int i, j;

		Point(int i, int j) {
			this.i = i;
			this.j = j;
		}

		@Override
		public int compareTo(Point p) {
			if (i == p.i)
				return j - p.j;
			return i - p.i;
		}
	}

 

나머지는 알아서 잘 구현해보도록!

<전체 소스코드>

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

public class Main {

	private static final int[][] move = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
	private static int[][] map;
	private static boolean[][] visit;
	private static int n, cnt, time, level = 2;
	private static Point point;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = parse(br.readLine());
		map = new int[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] = parse(st.nextToken());
				if (map[i][j] == 9) {
					map[i][j] = 0;
					point = new Point(i, j);
				}
			}
		} // end Input

		do {
			visit = new boolean[n][n];
		} while (bfs());

		System.out.println(time);

	}

	private static boolean bfs() {
		// p에서 시작하여 어디까지 도달해보자.
		Queue<Point> q = new LinkedList<>();
		PriorityQueue<Point> pq = new PriorityQueue<>();
		q.offer(point);
		visit[point.i][point.j] = true;

		int currTime = 1;
		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Point np = q.poll();
				// 현재 점에서 어느 방향으로 움직일 수 있을까?
				for (int k = 0; k < 4; k++) {
					int ni = np.i + move[k][0];
					int nj = np.j + move[k][1];

					// 움직일 수 있으면 일단 pq에 담는다.
					if (checkIdx(ni, nj) && !visit[ni][nj] && map[ni][nj] <= level) {
						visit[ni][nj] = true;

						// 먹을 수 있는곳은 pq에 담는다
						if (map[ni][nj] < level && map[ni][nj] != 0)
							pq.offer(new Point(ni, nj));
						q.offer(new Point(ni, nj));
					}
				}
			}

			// 움직일 수 있는 곳 중에서 먹을 수 있는 곳 있음
			while (!pq.isEmpty()) {
				Point p = pq.poll();
				cnt++;
				map[p.i][p.j] = 0;
				time += currTime;
				if (cnt >= level) {
					// 레벨 업 가능한 경우
					cnt %= level++;
				}
				point = p;
				return true;
			}
			currTime++;
		}
		return false;
	}

	// 인덱스 유효성 검사
	private static boolean checkIdx(int i, int j) {
		if (i >= 0 && j >= 0 && i < n && j < n)
			return true;
		return false;
	}

	static class Point implements Comparable<Point> {
		int i, j;

		Point(int i, int j) {
			this.i = i;
			this.j = j;
		}

		@Override
		public int compareTo(Point p) {
			if (i == p.i)
				return j - p.j;
			return i - p.i;
		}
	}

	private static int parse(String s) {
		return Integer.parseInt(s);
	}
}