[알고리즘] 백준 청소년 상어 19236 문제 풀이

www.acmicpc.net/problem/19236

19236번: 청소년 상어

아기 상어의 8방 버전입니다.

백트래킹을 사용해 풀면 리소스 사용량을 줄일 수 있겠다는 생각에 백트래킹으로 도전을 했지만 물고기의 이동과 상어, 먹힌 물고기등 관리해야 하는 변수가 많아 코드 작성이 힘들었습니다.

다 작성한 후 예상한 결과값과 출력값이 달랐지만 에러 추적이 쉽지 않았고 결국 다시 매 상태공간트리마다 새로운 배열과 물고기 리스트를 가지고 가는 형태로 작성하게 되었습니다.

해당 문제에 막혀있는 분들에게 제 코드가 실마리가 되었으면 좋겠고 백트래킹으로 도전해보시면 좋겠습니다.

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

public class Main {
	static class Fish{
		boolean isAlive;
		int x;
		int y;
		int dir;
		public Fish(boolean isAlive, int x, int y, int dir) {
			super();
			this.isAlive = isAlive;
			this.x = x;
			this.y = y;
			this.dir = dir;
		}
	}
	
	static class Shark{
		int score;
		int x;
		int y;
		int dir;
		public Shark(int score, int x, int y, int dir) {
			super();
			this.score = score;
			this.x = x;
			this.y = y;
			this.dir = dir;
		}
	}
	
	static int[][] pos = {{},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
	static int answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[][] arr = new int[4][4];
		Fish[] fishArr = new Fish[17];
		
		for (int i = 0; i < arr.length; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < arr[i].length; j++) {
				int num = Integer.parseInt(st.nextToken());
				int dir = Integer.parseInt(st.nextToken());
				
				arr[i][j] = num;
				fishArr[num] = new Fish(true, i, j, dir);
			}
		}
		
		Shark shark = new Shark(arr[0][0], 0, 0, fishArr[arr[0][0]].dir);
		fishArr[arr[0][0]].isAlive = false;
		arr[0][0] = -1;
		
		recur(arr, fishArr, shark);
		
		System.out.println(answer);
	}

	private static void recur(int[][] arr, Fish[] fishArr, Shark shark) {
		for (int i = 1; i < fishArr.length; i++) {
			if(!fishArr[i].isAlive) continue;
			
			Fish fish = fishArr[i];
			
			for (int j = 0; j < 8; j++) {
				int nr = fish.x + pos[fish.dir][0];
				int nc = fish.y + pos[fish.dir][1];
				
				if(posCheck(nr, nc) && arr[nr][nc] != -1) {
					if(arr[nr][nc] == 0) {
						arr[nr][nc] = i;
						arr[fish.x][fish.y] = 0;
						fish.x = nr;
						fish.y = nc;
					}else if(arr[nr][nc] > 0) {
						int targetIdx = arr[nr][nc];
						int targetX = fishArr[targetIdx].x;
						int targetY = fishArr[targetIdx].y;
						arr[nr][nc] = i;
						arr[fish.x][fish.y] = targetIdx;
						fishArr[targetIdx].x = fish.x;
						fishArr[targetIdx].y = fish.y;
						fish.x = targetX;
						fish.y = targetY;
					}
					break;
				}else {
					fish.dir = nextDir(fish.dir);
				}
			}// end for 8
		}// end for fishArr
		
		int nr = shark.x;
		int nc = shark.y;
		while(true) {
			nr += pos[shark.dir][0];
			nc += pos[shark.dir][1];
			
			if(!posCheck(nr, nc)) break;
			
			if(arr[nr][nc] > 0) {
				Shark nextShark = new Shark(shark.score, shark.x, shark.y, shark.dir);
				int[][] copyArr = copyArr(arr);
				Fish[] copyFishArr = copyFishArr(fishArr);
				
				copyArr[nextShark.x][nextShark.y] = 0;
				nextShark.x = nr;
				nextShark.y = nc;
				nextShark.dir = copyFishArr[copyArr[nr][nc]].dir;
				copyFishArr[copyArr[nr][nc]].isAlive = false;
				nextShark.score += copyArr[nr][nc];
				copyArr[nr][nc] = -1;
				
				answer = Math.max(answer, nextShark.score);
				recur(copyArr, copyFishArr, nextShark);
			}
		}
	}

	private static boolean posCheck(int row, int col) {
		return row >= 0 && row < 4 && col >= 0 && col < 4;
	}
	
	private static int nextDir(int dir) {
		if(++dir > 8) {
			dir = 1;
		}
		
		return dir;
	}
	
	private static int[][] copyArr(int[][] arr){
		int[][] copy = new int[4][4];
		
		for (int i = 0; i < copy.length; i++) {
			for (int j = 0; j < copy[i].length; j++) {
				copy[i][j] = arr[i][j];
			}
		}
		
		return copy;
	}
	
	private static Fish[] copyFishArr(Fish[] fishArr) {
		Fish[] copy = new Fish[fishArr.length];
		
		for (int i = 1; i < fishArr.length; i++) {
			Fish fish = fishArr[i];
			copy[i] = new Fish(fish.isAlive, fish.x, fish.y, fish.dir);
		}
		
		return copy;
	}
}