[백준] 19236 - 청소년 상어

[문제링크]

19236번: 청소년 상어

 

0. 백트래킹 / 구현 문제

 

1. 백트래킹을 위하여, 상어의 각 이동 단계마다 map과 물고기 방향 정보를 저장한다

 

2. 해당 상황에서 물고기 이동 - 가능한 모든 상어 이동에 대해 재귀를 돌린 다음, 저장해둔 정보를 복원하고 이전 단계로 돌아간다

 

3. 각 재귀 단계에서 먹은 물고기 번호의 합을 저장, 더이상 진행 불가능할때 전역변수인 maxEat과 비교, 갱신한다

 

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

public class Main{
	static int[][] dir = {
			{-1,0},{-1,-1},{0,-1},{1,-1},
			{1,0},{1,1},{0,1},{-1,1}
	};
	static int maxEat=0;
	static boolean[] deadFish;
	static int[][] fish;
	static int[][] map;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		map = new int[4][4];
		fish = new int[17][3];
		deadFish = new boolean[17];
		for (int i = 0; i < 4; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; j++) {
			
				int num = pint(st.nextToken());
				int dir = pint(st.nextToken());
				map[i][j]=num;
				fish[num][0]=i;
				fish[num][1]=j;
				fish[num][2]=dir-1;
			}
		}
		//fish[0] = shark
		deadFish[map[0][0]]=true;
		maxEat+=map[0][0];
		fish[0][2] = fish[ map[0][0] ][2];
		map[0][0]=-1;
		
		rec(maxEat);
		System.out.println(maxEat);
	}
	
	static void rec(int eat) {
		//comparemaxEat
		if(maxEat<eat)maxEat=eat;
		
		
		int[][]tmpMap = new int[4][4];
		int[][] tmpFish = new int[17][3];
		boolean[] tmpDeadFish = new boolean[17];
		//backup
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				tmpMap[i][j]=map[i][j];
			}
		}
		for (int i = 0; i < 17; i++) {
			tmpFish[i][0]=fish[i][0];
			tmpFish[i][1]=fish[i][1];
			tmpFish[i][2]=fish[i][2];
			tmpDeadFish[i]=deadFish[i];
		}

		//fish move
		for (int i = 1; i < 17; i++) {
			if(deadFish[i])continue;//죽었다면 넘어감
			
			int curX = fish[i][0], curY = fish[i][1], curDir = fish[i][2];
			for (int j = 0; j < 8; j++) {
				//ok?
				int nX = curX+dir[curDir][0];
				int nY = curY+dir[curDir][1];
				if(nX<0 || nY<0 || nX>=4 || nY>=4 || map[nX][nY]==-1) {
					curDir= (curDir+1)%8; continue;
				}
				
				//swap
				int tmp = map[nX][nY];
				map[nX][nY]=map[curX][curY];
				map[curX][curY]=tmp;
				
				fish[i][0]=nX;fish[i][1]=nY;
				fish[i][2]=curDir;

				if(tmp!=0) {
					fish[tmp][0]=curX;
					fish[tmp][1]=curY;
				}
				
				break;
			}
		}
		
		//shark move
		//eat
		map[ fish[0][0] ][ fish[0][1] ]=0;//빈 공간화
		while(true) {
			fish[0][0]+=dir[fish[0][2]][0];
			fish[0][1]+=dir[fish[0][2]][1];
			
			if(fish[0][0]<0 || fish[0][0]>=4 || fish[0][1]<0 || fish[0][1]>=4) {
				break;
			}
			if(map[fish[0][0]][fish[0][1]]==0)continue;
			
			int tmp = map[ fish[0][0] ][ fish[0][1] ];
			
			map[ fish[0][0] ][ fish[0][1] ]=-1;
			deadFish[tmp]=true;
			int tmpShakeDir = fish[0][2];
			fish[0][2]=fish[tmp][2];
			
			rec(eat+tmp);
			
			fish[0][2]=tmpShakeDir;
			map[ fish[0][0] ][ fish[0][1] ]=tmp;
			deadFish[tmp]=false;
		}
		
		//return
		//restore
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				map[i][j]=tmpMap[i][j];
			}
		}
		for (int i = 0; i < 17; i++) {
			fish[i][0]=tmpFish[i][0];
			fish[i][1]=tmpFish[i][1];
			fish[i][2]=tmpFish[i][2];
			deadFish[i]=tmpDeadFish[i];
		}
		return;
	}
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면