BOJ - 19237 어른 상어

19237 어른 상어 : https://www.acmicpc.net/problem/19237

---

Problem

---

Solve

상어의 영역 int[][] map, 상어의 냄새 int[][] range, 상어의 우선순위 움직임 int[][][]move

구현의 순서는 아래와 같다.
1. map, range, move 초기화
2. 1000번 반복, 1번 상어 한마리만 남게되면 해당 turn 반환.
3. 상어 움직임

• M개의 상어를 돌면서 isOut == true인 상어는 제외.
• 총 8번의 방향을 탐색한다.
  - 0~3번은 빈 좌표 탐색
  • 4~7번은 자신의 냄새 좌표 탐색
• 탐색 후 이동하려는 좌표에 이미 상어가 존재한다면 이동하려는 상어의 isOut = true로 갱신하고 해당 상어에 대한 움직임 함수를 종료한다.
  그렇지 않다면 상어의 위치와 방향 및 map 갱신

4. 상어의 각 냄새 -1 감소

• range에 있는 상어의 냄새를 -1씩 감소
• 만약 range[i][j]가 0이라면 map[i][j]에 상어의 영역 표시를 제거한다.

5. 현재 상어의 위치 냄새 초기화

• 현재 상어의 위치 range[i][j]와 map[i][j]에 해당 상어 번호를 갱신한다.

6. 남아있는 상어의 여부 확인

• 남아있는 상어의 개수가 1마리라면 함수 종료

---

Code

public class 어른상어 {
	static int[][] map;
	static int[][] range;
	static int[][][] move;

	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};

	static Shark[] sharks;
	static int N;
	static int M;
	static int K;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		range = new int[N][N];
		move = new int[M + 1][4][4];
		sharks = new Shark[M + 1];

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

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

		for (int s = 1; s < M + 1; s++) {
			for (int i = 0; i < 4; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < 4; j++) {
					move[s][i][j] = Integer.parseInt(st.nextToken()) - 1;
				}
			}
		}

		int answer = -1;
		int time = 0;
		while (time++ < 1000) {

			if (start()) {
				answer = time;
				break;
			}
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static boolean start() {
		//map : 상어, range : 냄새, move : 상어별 움직의 우선순위

		moveShark();

		boolean isOnlyStrongShark = true;
		//냄새 -1;
		disCountSmell();
        //상어가 이동한 좌표에 냄새 추가
		setSharkSmell();

		//out된 상어의 개수가 M-1개 일때 1번 상어만 남은것이므로 함수 종료
		int outCount = 0;
		for (int i = 2; i < M + 1; i++) {
			if (sharks[i].isOut) {
				outCount++;
			}
		}
		if (outCount < M - 1)
			isOnlyStrongShark = false;

		return isOnlyStrongShark;
	}

	static void setSharkSmell() {
		for (Shark shark : sharks) {
			if (shark == null)
				continue;
			if (shark.isOut)
				continue;

			range[shark.y][shark.x] = K;
			map[shark.y][shark.x] = shark.num;
		}
	}

	static void disCountSmell() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (range[i][j] != 0) {
					range[i][j]--;
					if (range[i][j] == 0)
						map[i][j] = 0;
				}
			}
		}
	}

	static void moveShark() {
		int[][] cloneMap = cloneArr(map);
		int[][] cloneRange = cloneArr(range);
		for (int s = 1; s < M + 1; s++) {
			Shark shark = sharks[s];
            //아웃된 상어라면 제외
			if (shark.isOut)
				continue;
            //8번의 방향 체크
			for (int i = 0; i < 8; i++) {
				int nd = move[shark.num][shark.d][i % 4];
				int ny = shark.y + dy[nd];
				int nx = shark.x + dx[nd];
				//빈 공간
				if (i < 4) {

					if (ny < N && nx < N && ny >= 0 && nx >= 0 && map[ny][nx] == 0) {
                    	//이동하려는 좌표에 상어가 있다면 이미 있는 상어의 번호가 더 높으므로 현재 이동중인 상어를 out
						if (cloneMap[ny][nx] != 0) {
							shark.isOut = true;
							break;
						}
						cloneMap[ny][nx] = shark.num;
						// cloneRange[ny][nx] = K;

						shark.d = nd;
						shark.y = ny;
						shark.x = nx;
						break;
					}
				}
				//자신 영역
				else {
					if (ny < N && nx < N && ny >= 0 && nx >= 0 && map[ny][nx] == shark.num) {
						cloneMap[ny][nx] = shark.num;
						// cloneRange[ny][nx] = K;

						shark.d = nd;
						shark.y = ny;
						shark.x = nx;
						break;
					}
				}
			}
		}
		map = cloneMap;
		range = cloneRange;
	}

	static int[][] cloneArr(int[][] arr) {
		int[][] cloneArr = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cloneArr[i][j] = arr[i][j];
			}
		}

		return cloneArr;
	}

	static class Shark {
		int num;
		int y;
		int x;
		int d;
		boolean isOut;

		public Shark(int num, int y, int x) {
			this.num = num;
			this.y = y;
			this.x = x;
			isOut = false;
		}
	}
}

---

Result

점점 조건이 까다롭고 시간도 많이 잡아먹는 상어..

---

Reference