문제

백준 - 청소년 상어

📝 풀이

백트래킹, 구현 문제였으며 깊은 복사를 통한 탐색을 통해 해결할 수 있는 문제였다.
다만, Java의 객체 참조를 다루는 것이 미숙하여 깊은 복사가 아닌 참조값 복사 코드를 작성하여 꽤나 고생하였다..😂😂😂

🔑 핵심

• 상어는 한 번에 여러 개의 칸을 이동할 수 있다.
  - 이동 칸 탐색 중 빈 칸이 있어도 격자 밖을 나가기 전까지는 계속 탐색해야 한다.

• 상어가 이동할 때 마다 격자 전체를 깊은 복사해야 한다.
  - 상어가 이동하고 물고기도 이동하기 때문에 상어가 이동하는 모든 경우에 대해 다른 격자를 생성해야 한다.

  • 격자 크기는 4 x 4 로 굉장히 작기 때문에 모든 경우에 대한 격자를 만들어도 메모리 제한 및 시간 제한을 넘지 않는다.

💻 초기 코드

• 주석을 적절한 위치에 없고 변수명이나 함수명의 가독성이 좋지 않다.
• new Fish의 긴 매개변수 반복 작성이 많다.

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

class Fish {
	int a, b;

	public Fish(int a, int b) {
		super();
		this.a = a;
		this.b = b;
	}

}

public class Main {

	static int[] shark = { 0, 0 };
	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 = 0;
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Fish[][] arr = new Fish[4][4];
		for (int i = 0; i < 4; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; j++) {
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				arr[i][j] = new Fish(a, b - 1);
			}
		}
		
		dfs(0, 0, arr[0][0].a, arr);
		
		System.out.println(ans);
		
	}
	
	// 상어는 (0, 0)에 있는 물고기 먹고 시작
	static void dfs(int sx, int sy, int fish, Fish[][] arr) {
		ans = Math.max(ans, fish);
		Fish copy = new Fish(arr[sx][sy].a, arr[sx][sy].b);
		arr[sx][sy] = null;
		fishMove(arr);
		
		int x = sx, y = sy;
		while (true) {
			int nx = x + dx[copy.b];
			int ny = y + dy[copy.b];
			if (0 > nx || 4 <= nx || 0 > ny || 4 <= ny)	break;
			if (arr[nx][ny] == null) {
				x = nx;
				y = ny;
				continue;
			}
			Fish tmp = new Fish(arr[nx][ny].a, arr[nx][ny].b);
			shark = new int[]{nx, ny};
			dfs(nx, ny, fish + arr[nx][ny].a, copy(arr));
			shark = new int[]{sx, sy};
			arr[nx][ny] = new Fish(tmp.a, tmp.b);
			x = nx;
			y = ny;
		}
		if (x == sx && y == sy) {
			return;
		}
		
	}
	
	// 물고기 번호가 작은 순부터 이동
	// 이동 칸에 상어 있으면 못 감
	// 갈 수 있는 칸 만날 때 까지 45도 반시계 회전 < 8번
	// 다른 물고기가 있는 곳으로 이동하면 서로의 값 바꾼다.
	static void fishMove(Fish[][] arr) {
		int number = 1;
		while (number < 17) {
			findFish(number++, arr);
		}
	}
	
	static void findFish(int number, Fish[][] arr) {
		boolean flag = false;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (arr[i][j] != null && arr[i][j].a == number) {
					int[] next = check(i, j, arr);
					Fish n = arr[next[0]][next[1]];
					arr[next[0]][next[1]] = new Fish(arr[i][j].a, arr[i][j].b);
					arr[i][j] = n;
					flag = true;
					break;
				}
			}
			if (flag)	break;
		}
	}
	
	private static int[] check(int x, int y, Fish[][] arr) {
		int nx = x, ny = y;
		for (int i = 0; i < 8; i++) {
			nx = x + dx[(arr[x][y].b + i) % 8];
			ny = y + dy[(arr[x][y].b + i) % 8];
			if (0 > nx || 4 <= nx || 0 > ny || 4 <= ny)	continue;
			if (nx == shark[0] && ny == shark[1])	continue;
			arr[x][y].b = (arr[x][y].b + i) % 8;
			break;
		}
		
		return new int[] {nx, ny};
		
	}
	
	private static  Fish[][] copy(Fish[][] fish) {
		Fish[][] copy = new Fish[4][4];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (fish[i][j] == null) {
					copy[i][j] = null;
					continue;
				}
				copy[i][j] = new Fish(fish[i][j].a, fish[i][j].b);
			}
		}
		return copy;
	}

}

💻 개선된 코드

• 주석을 적절히 위치하였고 변수명과 함수명도 직관적으로 변경했다.
• new Fish의 긴 매개변수 반복을 clone 함수를 선언하여 정리하였다.

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

class Fish {
	int num, dir;

	public Fish(int num, int dir) {
		super();
		this.num = num;
		this.dir = dir;
	}

}

public class Main {

	static int[] shark = { 0, 0 };
	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 = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Fish[][] arr = new Fish[4][4];
		for (int i = 0; i < 4; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; j++) {
				int num = Integer.parseInt(st.nextToken());
				int dir = Integer.parseInt(st.nextToken());
				arr[i][j] = new Fish(num, dir - 1);
			}
		}
		// 상어는 (0, 0)에 있는 물고기 먹고 시작
		sharkMove(0, 0, arr[0][0].num, arr);

		System.out.println(ans);

	}

	static void sharkMove(int sx, int sy, int fish, Fish[][] arr) {
		ans = Math.max(ans, fish);
		Fish ateFish = clone(arr[sx][sy]);
		arr[sx][sy] = null;
		fishMove(arr);

		int x = sx, y = sy;
		while (true) {
			// 먹은 물고기의 방향으로 이동
			int nx = x + dx[ateFish.dir];
			int ny = y + dy[ateFish.dir];

			// 범위를 벗어나거나 빈 칸은 갈 수 없다.
			if (0 > nx || 4 <= nx || 0 > ny || 4 <= ny)	break;
			if (arr[nx][ny] == null) {
				// 여러 개의 칸으로 이동
				x = nx;
				y = ny;
				continue;
			}

			// 물고기 발견!
			Fish eat = clone(arr[nx][ny]);
			shark = new int[] { nx, ny };
			sharkMove(nx, ny, fish + arr[nx][ny].num, copy(arr));
			shark = new int[] { sx, sy };
			arr[nx][ny] = clone(eat);

			// 여러 개의 칸으로 이동
			x = nx;
			y = ny;
		}

		if (x == sx && y == sy) {
			// 상어가 갈 곳이 없어 집으로 간다.
			return;
		}

	}

	// 물고기 번호가 작은 순부터 이동
	static void fishMove(Fish[][] arr) {
		int number = 1;
		while (number != 17) {
			findNumberEqualFish(number++, arr);
		}
	}

	static void findNumberEqualFish(int number, Fish[][] arr) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (arr[i][j] != null && arr[i][j].num == number) {
					// number에 해당하는 물고기 이동
					change(i, j, arr);
					return;
				}
			}
		}
	}

	// 갈 수 있는 칸 만날 때 까지 45도 반시계 회전 < 8번
	private static int[] fishMoveCheck(int x, int y, Fish[][] arr) {

		// 이동할 칸이 없는 경우도 존재
		int nx = x, ny = y;
		for (int i = 0; i < 8; i++) {
			nx = x + dx[(arr[x][y].dir + i) % 8];
			ny = y + dy[(arr[x][y].dir + i) % 8];
			if (0 > nx || 4 <= nx || 0 > ny || 4 <= ny)	continue;
			if (nx == shark[0] && ny == shark[1])	continue;
			arr[x][y].dir = (arr[x][y].dir + i) % 8;
			break;
		}

		return new int[] { nx, ny };

	}

	private static void change(int x, int y, Fish[][] arr) {
		// 물고기가 이동할 위치 반환
		int[] next = fishMoveCheck(x, y, arr);

		// 물고기가 이동하면 서로의 값 바꾼다.
		Fish change = arr[next[0]][next[1]];
		arr[next[0]][next[1]] = clone(arr[x][y]);
		arr[x][y] = change;
	}

	private static Fish[][] copy(Fish[][] fish) {
		Fish[][] copy = new Fish[4][4];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (fish[i][j] == null) {
					copy[i][j] = null;
					continue;
				}
				copy[i][j] = clone(fish[i][j]);
			}
		}
		return copy;
	}

	private static Fish clone(Fish fish) {
		return new Fish(fish.num, fish.dir);
	}

}