[백준] 19237. 어른 상어

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

19237번: 어른 상어

---

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

public class Main {

	static class Pair {
		int x;
		int y;

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

	static class Info {
		int n; // 상어 번호
		int t; // 남은 시간

		public Info(int n, int t) {
			this.n = n;
			this.t = t;
		}
	}

	static class Shark {
		int x;
		int y;
		int d;

		int[][] p;

		public Shark(int x, int y, int d, int[][] p) {
			this.x = x;
			this.y = y;
			this.d = d;
			this.p = p;
		}

		@Override
		public String toString() {
			System.out.println("** 상어의 현재 위치 : (" + x + ", " + y + ")");
			System.out.println("** 상어의 현재 이동 방향 : " + d);
			return "";
		}

	}

	static int N, M, k;
	static int[][] dir = { { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; // 위, 아래, 왼쪽, 오른쪽
	static Shark[] sharks;
	static Info[][] map;
	static ArrayList<Pair> list = new ArrayList();

	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());

		map = new Info[N + 1][N + 1];
		sharks = new Shark[M + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 1; j <= N; j++) {
				int value = Integer.parseInt(st.nextToken());
				if (value != 0) {
					sharks[value] = new Shark(i, j, 0, null);
				}
			}
		}

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

		for (int i = 1; i <= M; i++) {
			int[][] p = new int[5][5];
			for (int j = 1; j <= 4; j++) {
				st = new StringTokenizer(br.readLine(), " ");

				for (int k = 1; k <= 4; k++)
					p[j][k] = Integer.parseInt(st.nextToken());
			}
			sharks[i].p = p;
		}

		int TIME = 0;

		while (TIME <= 1000) {

			TIME++;
			
			// 1. 현재 상어 위치에 냄새 남기고 좌표 list에 넣기
			for(int i=1; i<=M; i++) {
				if (sharks[i] == null)
					continue;

				Shark s = sharks[i];
				
				map[s.x][s.y] = new Info(i, k);
				list.add(new Pair(s.x, s.y));
			}

			// 상어 이동 시키기
			for (int i = 1; i <= M; i++) {

				if (sharks[i] == null)
					continue;

				Shark s = sharks[i];

				int nx = 0, ny = 0, nd = 0;
				boolean flag = false;
				
				for (int j = 1; j <= 4; j++) {
					nx = s.x + dir[s.p[s.d][j]][0];
					ny = s.y + dir[s.p[s.d][j]][1];

					if (isInside(nx, ny) && map[nx][ny] == null) {
						flag = true;
						nd = s.p[s.d][j];
						break;
					}
				}

				if (flag) { // 상어가 빈칸으로 이동 할 수 있음
					sharks[i].x = nx;
					sharks[i].y = ny;
					sharks[i].d = nd;
				} else { // 상어가 이동할 수 있는 칸이 없다 -> 자신의 냄새가 있는 칸으로 방향을 잡는다.
					for (int j = 1; j <= 4; j++) {
						nx = s.x + dir[s.p[s.d][j]][0];
						ny = s.y + dir[s.p[s.d][j]][1];

						if (isInside(nx, ny) && map[nx][ny].n == i) {
							sharks[i].x = nx;
							sharks[i].y = ny;
							sharks[i].d = s.p[s.d][j];
							for (int k = 0; k < list.size(); k++) {
								if (list.get(k).x == nx && list.get(k).y == ny) {
									list.remove(k);
								}
							}
							break;
						}
					}
				}
			}

			// 0. 전에 남겼던 냄새 1초씩 깎기
			for (int j = 0; j < list.size(); j++) {
				Pair p = list.get(j);
				if (map[p.x][p.y].t - 1 == 0) {
					map[p.x][p.y] = null;
					list.remove(j);
					j--;
				} else {
					map[p.x][p.y].t--;
				}
			}

			// 3. 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 격자 밖으로 쫓아낸다.
			int[][] visited = new int[N + 1][N + 1];

			for (int i = 1; i <= M; i++) {
				if (sharks[i] == null)
					continue;
				Shark s = sharks[i];
				if (visited[s.x][s.y] == 0) {
					visited[s.x][s.y] = i;
				} else {
					sharks[i] = null;
				}
			}

			// 1번 상어만 살아있는지 검사
			boolean out = true;
			for (int i = 2; i <= M; i++) {
				if (sharks[i] != null) {
					out = false;
				}
			}

			if (out)
				break;

		}

		if (TIME == 1001)
			System.out.println(-1);
		else
			System.out.println(TIME);
	}

	public static boolean isInside(int x, int y) {
		return x >= 1 && x <= N && y >= 1 && y <= N;
	}
}