백준 19236 : 청소년 상어

문제 링크

---

접근 방법

시뮬레이션 문제이기 때문에 문제 그대로 풀었고 

물고기와 상어가 이동할 때 어떤 데이터가 필요한지 먼저 분석했다.

 

물고기의 이동

• 물고기 번호 순서대로 이동이 일어나야 한다 → 번호에 따른 물고기 위치 파악 

• 물고기의 좌표값이 교환된다

 

상어의 이동 

• 좌표에 있는 물고기의 번호를 알아야 한다 → 위치에 따른 물고기 번호 파악

 

우선 물고기 정보(x, y, 방향)을 담는 Fish 클래스를 선언하고

정보를 관리하는 배열 Fish[]를 만들어서 물고기 번호로 위치와 방향을 알 수 있게 만들었다.

또한, int[][] map에는 해당 좌표의 물고기의 번호를 저장하였다.

 

물고기의 이동시 Fish[]를 순서대로 보면서 갈 수 있는 위치라면 위치를 교환해주고 방향값을 갱신하였다.

상어의 이동시 갈 수 있는 위치라면 그 위치의 물고기 정보를 null로 바꾼 후 recursion 호출을 해주었다.

---

삽질했던 부분

1. 물고기의 바뀐 방향값 갱신

디버깅하기 전에 문제를 한 번 더 읽자...

 

2. 배열을 함수의 인자로 전달할 때 필요했던 깊은 복사

배열은 reference type이기 때문에 중간 재귀 호출 시 값을 변경하게 되면 생각한대로 동작하지 않게 된다.

따라서 재귀 호출시 매번 배열을 복사하고 인자로 전달해야 했으며 깊은 복사를 수행해야 했다.

 

int[][] 배열을 clone을 이용하여 복사를 하고

Fish[] 배열 또한 별생각 없이 clone을 이용하여 복사를 했는데 얉은 복사가 일어났다. (당연함)

다시 생성자도 만들고 깊은 복사를 해주었더니 잘 동작하였다.

---

후기

디버깅을 매우 많이 했지만 삽질이 없었다면 적당한 시간에 풀었을 것 같은 문제였다.

배열을 파라미터로 넘기고 재귀를 호출했을 때 어떤 점을 주의해야 하는지 배울 수 있어서 좋은 문제였다.

 

---

코드

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

/*
 *  19236. 청소년 상어
 *  https://www.acmicpc.net/problem/19236
 *  시뮬레이션 문제! 배열을 파라미터로 넘길 때 주의하자!
 */
public class 청소년상어19236 {
	static int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int dy[] = { 0, -1, -1, -1, 0, 1, 1, 1 };
	static int ans;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int[][] map = new int[4][4]; // 해당 위치에 위치하는 물고기의 번호를 저장하는 지도
		Fish[] fish = new Fish[16]; // 물고기의 번호로 접근하여 위치와 방향을 알 수 있는 배열
		for (int i = 0; i < 4; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; j++) {
				int a = Integer.parseInt(st.nextToken()) - 1;
				int b = Integer.parseInt(st.nextToken()) - 1;
				fish[a] = new Fish(i, j, b);
				map[i][j] = a;
			}
		}
		Fish shark = fish[map[0][0]];
		fish[map[0][0]] = null;
		simulation(map, fish, shark, map[0][0] + 1);
		System.out.println(ans);
	}

	static void simulation(int[][] map, Fish[] fish, Fish shark, int cnt) {
		// 상어가 더 갈 수 없다면 물고기 이동 전에 끝낸다
		int x = shark.x + dx[shark.d];
		int y = shark.y + dy[shark.d];
		if (x < 0 || y < 0 || x >= 4 || y >= 4) {
			ans = Math.max(ans, cnt);
			return;
		}
		// 물고기의 이동
		for (int i = 0; i < 16; i++) {
			if (fish[i] == null)
				continue;
			Fish f = fish[i];
			for (int d = f.d, k = 0; k < 8; d = (d + 1) % 8, k++) {
				int nx = f.x + dx[d];
				int ny = f.y + dy[d];
				if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || (nx == shark.x && ny == shark.y))
					continue;
				// 물고기 방향 update
				fish[i].d = d;

				// 물고기 위치를 교환하자
				// 1. map 세팅
				int j = map[nx][ny];
				map[nx][ny] = i;
				map[f.x][f.y] = j;

				// 2. fish[] 세팅 : j번과 i번 좌표를 swap
				fish[i].x = nx;
				fish[i].y = ny;
				if (fish[j] != null) {
					fish[j].x = nx - dx[d];
					fish[j].y = ny - dy[d];
				}
				break;
			}
		}
		// 상어의 이동
		for (int i = 1; i <= 3; i++) {
			int nx = shark.x + (dx[shark.d] * i);
			int ny = shark.y + (dy[shark.d] * i);
			if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) // 범위를 벗어나면 종료
				break;
			if (fish[map[nx][ny]] == null) // 해당 위치에 물고기가 없다면 다음으로
				continue;

			// fish의 깊은 복사
			Fish[] nfish = new Fish[16];
			for (int j = 0; j < 16; j++) {
				if (fish[j] == null)
					nfish[j] = null;
				else
					nfish[j] = new Fish(fish[j]);
			}
			nfish[map[nx][ny]] = null; // 상어가 물고기를 먹음

			// map의 깊은 복사
			int[][] nmap = new int[4][4];
			for (int j = 0; j < 4; j++)
				nmap[j] = map[j].clone();
			simulation(nmap, nfish, fish[map[nx][ny]], cnt + map[nx][ny] + 1);
		}
		ans = Math.max(ans, cnt);
	}

	static class Fish {
		int x, y, d;

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

		public Fish(Fish fish) {
			this.x = fish.x;
			this.y = fish.y;
			this.d = fish.d;
		}
	}
}