[백준] 19237번 / Java / 어른상어

문제 - (www.acmicpc.net/problem/19237)

 

🤔문제 접근 방법

상어마다 상하좌우 우선순위가 있네?->상어 클래스에 dir(현재 상어가 바라보는 방향), dirs(이 상어만의 우선순위)를 저장시켜 놓자

 

각 상어들 이동은 어떻게 하지?

• 다른 상어의 냄새가 없는 곳이 발견되면
  • 그 위치로 이동한다
    • 여기서 주의할 점!!! 그냥 이동하면 안 된다. tmp에 원래 map을 복사해놓고, tmp에다가 상어의 위치를 업데이트한다! 그랬을 때, 동시에 동일한 칸으로 이동하는 상어가 생긴다면, 상어의 숫자를 보고 판단하여 숫자가 가장 작은 상어만 이동시키고 나머지 상어는 모두 제거해준다. (반복문을 다 돌고 난 다음 제거작업 진행)
• 상하좌우 모두에 상어의 냄새가 존재한다면
  • 나의 우선순위 순서로 방문했을 때, 가장 먼저 발견된 나의 냄새가 있는 위치로 이동

 

---

📌주의할 점

• 개인적으로 까다로운 시뮬레이션 문제였다. 까다로울수록 설계단계에 시간을 많이 투자해서 꼼꼼하게 계획을 세운 뒤 코딩해야 한다...!! 이번에도 대충 설계한 뒤 코드로 바로 옮기는 바람에 디버깅하느라 시간을 너무 많이 뺏겼다. 주의하자.

 

---

코드

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

public class Main {
	static int N, M, K;
	static ArrayList<Shark> list;
	static Point[][] map;
	static int[] dy = { 0, -1, 1, 0, 0 };
	static int[] dx = { 0, 0, 0, -1, 1 };
	// 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미

	static class Point {
		int shark;
		int k;

		public Point(int shark, int k) {
			this.shark = shark;
			this.k = k;
		}
	}

	static class Shark {
		int num;
		int y;
		int x;
		int dir;
		int[][] dirs;

		public Shark(int num, int y, int x) {
			this.num = num;
			this.y = y;
			this.x = x;
			this.dirs = new int[5][];
		}
	}

	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()); // (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)
		M = Integer.parseInt(st.nextToken()); // 상어 1~M 번호 붙여 있음
		K = Integer.parseInt(st.nextToken());
		list = new ArrayList<>();
		map = new Point[N][N];// NxN map
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int cur = Integer.parseInt(st.nextToken());
				if (cur == 0) {
					map[i][j] = new Point(0, 0);
				} else {
					list.add(new Shark(cur, i, j));
					map[i][j] = new Point(cur, K);// 상어는 자신의 위치에 냄새 뿌림
				}
			}
		}

		list.sort((o1, o2) -> {
			return Integer.compare(o1.num, o2.num);
		});

		// 상어의 처음 방향
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			list.get(i).dir = Integer.parseInt(st.nextToken());
		}

		// 각 상어의 우선순위
		for (int i = 0; i < M; i++) {// M개 칸에 상어 한마리씩 존재
			for (int j = 1; j <= 4; j++) {
				st = new StringTokenizer(br.readLine());
				list.get(i).dirs[j] = new int[] { 0, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
						Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
			}
		}

		System.out.println(simulate());// 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램

		// 상어1 가장 강력해서 모두 쫓아냄

		// k번 이동 시 냄새 사라짐

	}

	private static int simulate() {
		int timer = 0;

		while (list.size() > 1) {
//			printMap();
			if(timer >= 1000) return -1;

			// 매 초마다 tmp 맵이 필요함
			Point[][] tmp = deepCopy(map);

			int size = list.size();
			ArrayList<Integer> removeShark = new ArrayList<>();
			loop: for (int i = 0; i < size; i++) {
				Shark shark = list.get(i);
				int sharkNum = shark.num;
				int y = shark.y;
				int x = shark.x;
				int dir = shark.dir;
				int[][] dirs = shark.dirs;

				// 1초 후 상하좌우 하나로 이동
				int my = -1;
				int mx = -1;
				int md = -1;
				boolean find = false;

				for (int d = 1; d <= 4; d++) {
					int ny = y + dy[dirs[dir][d]];
					int nx = x + dx[dirs[dir][d]];

					if (ny < 0 || nx < 0 || ny >= N || nx >= N) // 맵 밖으로 벗어나면 컨티뉴
						continue;

					// 상어 이동 방향 결정 시, 먼저 인접한 칸 중 아무 냄새 없는 칸 이동
					if (map[ny][nx].k == 0) { // 아무 냄새 없는 칸이면 바로 이동
						// 가능한 칸 여러개 일 시,특정한 우선순위 존재. 상어마다 다름. 상어가 보는 방향에 따라 다름.
						if (tmp[ny][nx].k != 0) { // 한 칸에 여러마리 있으면 가장 작은 번호만남음
							if (tmp[ny][nx].shark > sharkNum) {
								removeShark.add(tmp[ny][nx].shark);// 원래 tmp 에 있던 상어 쫓겨남
								shark.dir = dirs[dir][d]; // 이동한 방향이 보고있는 방향이 됨
								shark.y = ny; // 상어 위치 이동
								shark.x = nx;
								tmp[ny][nx].shark = sharkNum;
								tmp[ny][nx].k = K + 1;
							} else {
								removeShark.add(sharkNum);// 지금 상어 쫓겨남
							}
						} else { // 비어있다면 이동시킴
							shark.dir = dirs[dir][d]; // 이동한 방향이 보고있는 방향이 됨
							shark.y = ny; // 상어 위치 이동
							shark.x = nx;
							tmp[ny][nx].shark = sharkNum;
							tmp[ny][nx].k = K + 1;
						}
						continue loop;
					} else if (!find && map[ny][nx].shark == sharkNum) {
						my = ny;
						mx = nx;
						md = d;
						find = true; // 가장 처음 발견된 나의 냄새가 있던 곳을 기록하기 위한 플래그
					}
				}

				// 아무 냄새 없는 칸이 없었다면 자신의 냄새가 있던 칸으로 이동
				shark.dir = dirs[dir][md];
				shark.y = my;
				shark.x = mx;
				tmp[my][mx].k = K + 1;
			} // end of for

			// map 업데이트
			map = tmp;

			// map의 시간 k값 모두 1씩 내림
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j].k > 0)
						map[i][j].k--;
					else
						map[i][j].k = 0;
				}
			}

			// 쫓겨난 상어 제거
			for (int i = 0; i < removeShark.size(); i++) {
				int cur = removeShark.get(i);

				for (Iterator iterator = list.iterator(); iterator.hasNext();) {
					Shark shark = (Shark) iterator.next();
					if (shark.num == cur) {
						iterator.remove();
						continue;
					}
				}
			}

			timer++;
		}

		return timer;
	}

	private static void printMap() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print("[" + map[i][j].shark + "," + map[i][j].k + "]");
			}
			System.out.println();
		}
		System.out.println("---------------------");
	}

	private static Point[][] deepCopy(Point[][] origin) {
		Point[][] ret = new Point[N][N];
		for (int i = 0; i < origin.length; i++) {
			for (int j = 0; j < origin[i].length; j++) {
				ret[i][j] = new Point(origin[i][j].shark, origin[i][j].k);
			}
		}
		return ret;
	}

}