[백준] 19237번 어른 상어 (Java)

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

 

---

 

정답 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, K;
	static int[][][] board;
	static int[][][] direction;
	static int[][] sharks;
	static boolean[] alive;
	static int step = 0;
	static ArrayDeque<int[]> smell = new ArrayDeque<>();

	static int[] di = { 0, -1, 1, 0, 0 };
	static int[] dj = { 0, 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		board = new int[N][N][2];
		direction = new int[M + 1][5][5];
		sharks = new int[M + 1][3];
		alive = new boolean[M + 1];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < N; j++) {
				int number = Integer.parseInt(st.nextToken());
				if (number != 0) {
					sharks[number][0] = i;
					sharks[number][1] = j;
					alive[number] = true;
				}
			}
		}

		st = new StringTokenizer(br.readLine());
		for (int number = 1; number < M + 1; number++) {
			sharks[number][2] = Integer.parseInt(st.nextToken());
		}

		for (int number = 1; number < M + 1; number++) {
			for (int i = 1; i < 5; i++) {
				st = new StringTokenizer(br.readLine());

				for (int j = 1; j < 5; j++) {
					direction[number][i][j] = Integer.parseInt(st.nextToken());
				}
			}
		}

		spreadSmell();
		while (!allDied() && step <= 1000) {
			// 시작 위치에 냄새 뿌림

			for (int time = 0; time < K; time++) {
				if (allDied()) {
					break;
				}
				
				moveShark();
				step++;
			}
		}

		if (step > 1000) {
			System.out.println(-1);
		} else {
			System.out.println(step);
		}
	}

	private static void moveShark() {
		ArrayDeque<int[]> queue = new ArrayDeque<>();
		// 갈 좌표 체크하고
		for (int number = 1; number < M + 1; number++) {
			if (!alive[number])
				continue;
			
			int[] info = sharks[number];
			int ci = info[0];
			int cj = info[1];
			int cd = info[2];
			boolean moved = false;

			for (int i = 1; i < 5; i++) {
				int d = direction[number][cd][i];
				int ni = ci + di[d];
				int nj = cj + dj[d];

				if (validate(ni, nj)) {
					if (board[ni][nj][1] == 0) {
						queue.offer(new int[] { number, ni, nj, d });
						moved = true;
						break;
					}
				}
			}

			if (!moved) {
				for (int i = 1; i < 5; i++) {
					int d = direction[number][cd][i];
					int ni = ci + di[d];
					int nj = cj + dj[d];

					if (validate(ni, nj)) {
						if (board[ni][nj][0] == number) {
							queue.offer(new int[] { number, ni, nj, d });
							break;
						}
					}
				}
			}
		}

		decreaseSmell();
		while (!queue.isEmpty()) {
			int[] info = queue.poll();
			int number = info[0];
			sharks[number][0] = info[1];
			sharks[number][1] = info[2];
			sharks[number][2] = info[3];
		}

		deleteDuplicated();
		spreadSmell();
	}

	private static boolean validate(int ni, int nj) {
		return 0 <= ni && ni < N && 0 <= nj && nj < N;
	}

	private static void deleteDuplicated() {
		HashMap<Point, PriorityQueue<Integer>> pq = new HashMap<>();

		for (int number = 1; number < M + 1; number++) {
			if (!alive[number])
				continue;
			int si = sharks[number][0];
			int sj = sharks[number][1];

			pq.putIfAbsent(new Point(si, sj), new PriorityQueue<>());
			pq.get(new Point(si, sj)).offer(number);
		}

		for (Entry<Point, PriorityQueue<Integer>> entry : pq.entrySet()) {
			PriorityQueue<Integer> queue = entry.getValue();

			Integer smallest = null;
			while (!queue.isEmpty()) {
				Integer current = queue.poll();
				if (alive[current]) {
					smallest = current;
					break;
				}
			}

			if (smallest != null) {
				alive[smallest] = true;
			}

			while (!queue.isEmpty()) {
				Integer number = queue.poll();
				if (alive[number]) {
					alive[number] = false;
				}
			}
		}
	}

	private static void decreaseSmell() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j][1] > 0) {
					board[i][j][1]--;
				}

				if (board[i][j][1] == 0) {
					board[i][j][0] = 0;
				}
			}
		}
	}

	private static void spreadSmell() {
		for (int number = 1; number < M + 1; number++) {
			if (alive[number]) {
				board[sharks[number][0]][sharks[number][1]][0] = number;
				board[sharks[number][0]][sharks[number][1]][1] = K;
				smell.offer(new int[] { sharks[number][0], sharks[number][1], K });
			}
		}
	}

	private static boolean allDied() {
		for (int i = 2; i < M + 1; i++) {
			if (alive[i]) {
				return false;
			}
		}
		return true;
	}
}