백준 : 19237 어른상어 java

www.acmicpc.net/problem/19237

19237번: 어른 상어

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class B19237 {
	static int N, M, K;
	static int shark[][];
	static int smell[][][];
	static ArrayList<Integer>[][] map;
	static int priority[][][];
	static int dy[] = { 0, -1, 1, 0, 0 };
	static int dx[] = { 0, 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		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());

		/*
		 * init
		 */

		priority = new int[M + 1][5][4];
		map = new ArrayList[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				map[i][j] = new ArrayList<Integer>();
			}
		}
		shark = new int[M + 1][3];
		smell = new int[N + 1][N + 1][2];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				int num = Integer.parseInt(st.nextToken());
				if (num != 0) {
					map[i][j].add(num);
					shark[num][0] = i;
					shark[num][1] = j;
				}
			}
		}

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

		for (int m = 1; m <= M; m++) {
			for (int d = 1; d <= 4; d++) {
				st = new StringTokenizer(br.readLine());
				for (int p = 0; p < 4; p++)
					priority[m][d][p] = Integer.parseInt(st.nextToken());
			}
		}

		System.out.println(Solve());
	}

	private static int Solve() {
		int cnt = M;
		for (int t = 0; t <= 1000; t++) {
//			print();

			// 가장 작은 상어빼고 다죽이기
			cnt -= kill();
			// 냄새를 1씩 깐다
			removeSmell();
			// 자신의 위치에 냄새를 뿌린다.
			createSmell();
			// 모든 상어 상하 좌우로 이동
			for (int m = 1; m <= M; m++) {
				if (shark[m][0] == -1)
					continue;
				Move(m);
			}
			if (cnt == 1)
				return t;

		}

		return -1;
	}

	private static void print() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				System.out.print(map[i][j].size() + " ");
			}
			System.out.println();
		}
		System.out.println();

	}

	private static int kill() {
		int killCnt = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (map[i][j].size() >= 2) {
					int minShark = map[i][j].get(0);
					for (int k = 1; k < map[i][j].size(); k++) {
						if (minShark > map[i][j].get(k)) {
							minShark = map[i][j].get(k);
						}
					}
					for (int k = 0; k < map[i][j].size(); k++) {
						if (minShark == map[i][j].get(k))
							continue;
						shark[map[i][j].get(k)][0] = -1;
					}

					killCnt += (map[i][j].size() - 1);
					map[i][j].clear();
					map[i][j].add(minShark);
				}
			}
		}
		return killCnt;

	}

	private static void Move(int m) {
		int y = shark[m][0];
		int x = shark[m][1];
		int d = shark[m][2];

		map[y][x].clear();

		// 우선 순위 가기 빈공간
		for (int p = 0; p < 4; p++) {
			int nd = priority[m][d][p];
			int ny = y + dy[nd];
			int nx = x + dx[nd];
			if (ny < 1 || nx < 1 || ny > N || nx > N)
				continue;
			if (smell[ny][nx][0] == 0) {
				map[ny][nx].add(m);
				shark[m][0] = ny;
				shark[m][1] = nx;
				shark[m][2] = nd;
				return;
			}
		}

		// 같은 공간 가기
		for (int p = 0; p < 4; p++) {
			int nd = priority[m][d][p];
			int ny = y + dy[nd];
			int nx = x + dx[nd];
			if (ny < 1 || nx < 1 || ny > N || nx > N)
				continue;
			if (smell[ny][nx][0] == m) {
				shark[m][0] = ny;
				shark[m][1] = nx;
				shark[m][2] = nd;
				map[ny][nx].add(m);
				return;
			}
		}

	}

	// 냄새 뿌리기
	public static void createSmell() {
		for (int m = 1; m <= M; m++) {
			if (shark[m][0] == -1)
				continue;
			smell[shark[m][0]][shark[m][1]][0] = m;
			smell[shark[m][0]][shark[m][1]][1] = K;
		}
	}

	// 냄새 1 제거
	private static void removeSmell() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (smell[i][j][0] != 0) {
					smell[i][j][1]--;

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