[BOJ 23290] 마법사 상어와 복제(Java)

---

문제

마법사 상어와 복제

---

문제 해설

삼성 기출문제인 마법사 상어 시리즈이다.
마법사 시리즈 문제는 구현할 내용을 간단히 정리하고, 문제에서 주어지지 않은 엣지 케이스를 가정하는 것이 중요하다.

구현 내용 정리

1. 복제

• 물고기가 담겨있는 board를 순회하며 Queue에 물고기의 정보들을 담아놓고 5번에서 한번에 복제하도록 한다.
• 물고기의 정보는 위치와 direction이 존재하므로 객체로 만들어 저장하도록 한다.

2. 물고기 이동

• 상어, 냄새, 범위를 벗어나는 곳은 넘어가지 못하며 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 의 순서를 따른다.
• 이동할 수 있을때까지 반시계 회전을 하며 이동할 수 없는 경우 이동하지 않는다.
• 이 역시 순서대로 이동하면 2차원 배열 순회로 인해 이동한 물고기가 다시 이동하는 경우가 존재하기 때문에 Queue나 ArrayList에 담아놓고 한번에 이동하도록 한다.

3. 상어 이동

• 총 3칸을 이동하며 물고기를 가장 많이 먹는 방법으로 이동한다.
• 만약 물고기를 가장 많이 먹는 방법이 여럿이면, 사전 순서를 따른다.
• 그러므로 dx,dy 배열을 ↑,←,↓,→ 순으로 만들어 구현한다.
• 3칸을 이동해 경로에 존재하는 모든 물고기를 격자에서 제외하고 냄새를 남긴다.
• 4번의 냄새 제거를 위해 이 구간에서 제외된 물고기는 3의 냄새를 가지도록 한다.

4. 냄새 제거

• 전에 존재하는 냄새를 제거한다.

5. 물고기 복제

• 1에서 담았던 물고기를 복제한다.

---

Question

• 상어 이동시 첫 자리에 존재하는 물고기는 제외되는가?
  첫 자리에 존재하는 물고기는 제외된다.

• 물고기가 모든 방향 이동 불가시, 현 자리에 냄새가 존재하면 어떻게 되는가?
  현 자리에서 머문다

내가 생각한 엣지 케이스는 이 두 가지이다. 이런 엣지케이스가 궁금하다면 직접 해보던가, 문제를 천천히 다시 읽는 수 밖에 없다.

---

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	// 4:00 ~ 5:58
	static int[] dx = { 0, -1, -1, -1, 0, 1, 1, 1 }; // 물고기 방향
	static int[] dy = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] ddx = { -1, 0, 1, 0 }; // 상어 방향
	static int[] ddy = { 0, -1, 0, 1 };
	static int sharkX, sharkY; // 상어 위치
	static boolean[][] visited = new boolean[4][4]; // 상어 이동 방문체크
	static int m, s;
	static int eat = -1; // 상어가 현재 몇마리를 먹었는지 저장
	static String path = ""; // 어떤 경로로 상어가 이동할지 저장
	static Queue<Fish>[][] board; // 현재 맵 상태를 담아 놓을 큐
	static Queue<Fish> dupQ = new LinkedList<>(); // 0번에서 물고기 복제 상태를 담을 큐
	static int[][] smell = new int[4][4];

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

		// init
		m = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
		board = new LinkedList[4][4];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				board[i][j] = new LinkedList<>();
			}
		}
		// 물고기 정보 받기
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			Fish fish = new Fish(x - 1, y - 1, d - 1);
			board[x - 1][y - 1].offer(fish);
		}
		// 상어 위치 받기
		st = new StringTokenizer(br.readLine());
		sharkX = Integer.parseInt(st.nextToken()) - 1;
		sharkY = Integer.parseInt(st.nextToken()) - 1;

		for (int i = 0; i < s; i++) {
			// start
			// 1. 물고기 저장 - 모든 큐를 다 돌아 복제한다.
			saveFish();
			// 2. 물고기 이동
			moveFish();
			// 3. 상어 이동
			moveShark();
			// 4. 냄새 제거
			removeSmell();
			// 5. 물고기 복제
			dupFish();
		}
		int cnt = 0;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				cnt += board[i][j].size();
			}
		}
		System.out.println(cnt);
	}

	static void dupFish() {
		while (!dupQ.isEmpty()) {
			Fish fish = dupQ.poll();
			board[fish.x][fish.y].offer(fish);
		}
	}

	static void removeSmell() {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				smell[i][j] = Math.max(0, smell[i][j] - 1);
			}
		}
	}

	static void moveShark() {
		eat = -1;
		findPath(0, 0, "", sharkX, sharkY);
		// 경로대로 움직인다.
		for (int i = 0; i < 3; i++) {
			boolean flag = false;
			int dir = Integer.parseInt(path.substring(i, i + 1));
			int nx = sharkX + ddx[dir];
			int ny = sharkY + ddy[dir];
			// 물고기 제외
			while (!board[nx][ny].isEmpty()) {
				flag = true;
				board[nx][ny].poll();
			}
			// 냄새 기록
			if (flag)
				smell[nx][ny] = 3;
			// 상어 위치 이동
			sharkX = nx;
			sharkY = ny;
		}
	}

	// 물고기를 가장 많이 먹는 경로 찾기
	static void findPath(int depth, int cnt, String dir, int x, int y) {
		if (depth == 3) {
			if (cnt > eat) {
				eat = cnt;
				path = dir;
			}
			return;
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + ddx[i];
			int ny = y + ddy[i];
			// 범위 핸들링
			if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) {
				continue;
			}
			// 이미 방문했으면 물고기는 존재하지 않을 것.
			if (visited[nx][ny]) {
				findPath(depth + 1, cnt, dir + i, nx, ny);
			} else {
				visited[nx][ny] = true;
				findPath(depth + 1, cnt + board[nx][ny].size(), dir + i, nx, ny);
				visited[nx][ny] = false;
			}
		}
	}

	static void moveFish() {
		// 한번에 이동시켜야 하기 때문에 맵에 존재하는 모든 물고기를 빼야한다.
		// 뺀 뒤 자료구조에 담는다.
		ArrayList<Fish> arr = new ArrayList<>();

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				label: while (!board[i][j].isEmpty()) {
					Fish fish = board[i][j].poll();
					for (int k = 0; k < 8; k++) {
						int nx = fish.x + dx[(fish.d - k + 8) % 8];
						int ny = fish.y + dy[(fish.d - k + 8) % 8];
						// 범위, 상어, 냄새
						if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || (nx == sharkX && ny == sharkY)
								|| smell[nx][ny] > 0) {
							continue;
						}
						// 갈 수 있는 경우
						arr.add(new Fish(nx, ny, (fish.d - k + 8) % 8));
						continue label;
					}
					// 갈 수 없는 경우
					arr.add(fish);
				}
			}
		}
		// 다시 맵에 물고기 넣기
		for (Fish fish : arr) {
			board[fish.x][fish.y].offer(fish);
		}
	}

	static void saveFish() {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				int size = board[i][j].size();
				for (int k = 0; k < size; k++) {
					Fish fish = board[i][j].poll();
					dupQ.offer(fish);
					board[i][j].offer(fish);
				}
			}
		}
	}

	static class Fish {
		int x, y, d;

		Fish(int x, int y, int d) {
			this.x = x;
			this.y = y;
			this.d = d;
		}

	}
}

---