[백준 - 19236] 골드3 - 청소년 상어

1. 유형

시뮬레이션, 재귀

 

2. 풀이

상어가 이동할 수 있는 곳이 여러곳이기 때문에 dfs를 사용해야 한다.

이동 할때마다 새로운 맵이 필요해서 깊은 복사를 해야한다.

 

 

3. 코드

package 구현.삼성역태;

import java.util.Scanner;

public class back_청소년상어 {
	static int ans=0;
	static int dr[] = {-1,-1,0,1,1,1,0,-1};
	static int dc[] = {0,-1,-1,-1,0,1,1,1,};
	static class Pair{
		int r,c,d;
		public Pair(int r,int c,int d) {
			this.r=r;
			this.c=c;
			this.d=d;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int map[][] = new int[4][4];
		Pair fish[] = new Pair[17];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				map[i][j] = sc.nextInt();
				fish[map[i][j]] = new Pair(i,j, sc.nextInt()-1);
			}
		}
		int eat = map[0][0];
		Pair shark = new Pair(0,0,fish[map[0][0]].d);
		fish[map[0][0]].d = -1;
		map[0][0] = -1;
		dfs(map, fish, eat, shark);
		System.out.println(ans);
	}
	static void dfs(int[][] map, Pair fish[], int eat, Pair shark) {

		int mapCpy[][] = new int[4][4];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				mapCpy[i][j] = map[i][j];
			}
		}
		Pair fishCpy[] = new Pair[17];
		for (int i = 1; i < 17; i++) {
			fishCpy[i] = new Pair(fish[i].r,fish[i].c,fish[i].d);
		}
		for (int i = 1; i < 17; i++) {
			//죽은거나 상어가 아니어야해
			Pair cur = fishCpy[i];
			if(fishCpy[i].d==-1) continue;
			//다음좌표를 구해
			int d = cur.d;
			for (int j = 0; j < 8; j++) {
				int nr = cur.r+dr[d];
				int nc = cur.c+dc[d];
				if(nr<0 || nr>=4 || nc<0 || nc>=4 || mapCpy[nr][nc]==-1) {
					d=(d+1)%8;
					fishCpy[i].d=d;
					continue;
				}
				if(mapCpy[nr][nc]==0) {
					//map 다음좌표에 현재 물고기 넣고 지금 자리엔 0넣기
					mapCpy[nr][nc] = i;
					mapCpy[cur.r][cur.c] = 0;
					//fishcpy의 좌표값 갱신
					fishCpy[i] = new Pair(nr,nc,cur.d);
					break;
				}
				if(mapCpy[nr][nc]>0) {
					//mapcpy의 다음좌표 현 좌표 값끼리 스왑
					int nextfish = mapCpy[nr][nc];
					mapCpy[cur.r][cur.c] = nextfish;
					mapCpy[nr][nc] = i;
					//fishcpy끼리 스왑하기
					int a = fishCpy[i].d;
					int b= fishCpy[nextfish].d;
					fishCpy[i] = new Pair(nr,nc,a);
					fishCpy[nextfish] = new Pair(cur.r, cur.c, b);
					break;
				}
			}
		}
		for (int i = 1; i <= 3; i++) {
			int nr = shark.r + (dr[shark.d])*i;
			int nc = shark.c + (dc[shark.d])*i;
			if(nr<0 || nr>=4 || nc<0 || nc>=4 || mapCpy[nr][nc]==0) continue;
			
			int t = mapCpy[nr][nc];
			Pair s = new Pair(nr,nc, fishCpy[t].d);
			fishCpy[t].d = -1;
			//map 다음 좌표에 -1
			mapCpy[nr][nc] = -1;
			//map 현 좌표에 0
			mapCpy[shark.r][shark.c] = 0;
			//상어가 먹었으니 다음좌표 fishcpy의 d는 -1
			//재귀
			
			dfs(mapCpy, fishCpy, eat+t, s);
			//다음좌표 fishcpy원상복귀
			fishCpy[t] = new Pair(nr ,nc , s.d);
			//현좌표 mapcpy -1
			mapCpy[shark.r][shark.c] = -1;
			//다음좌표에 물고기 넣기
			mapCpy[nr][nc] = t;
		}
		ans = ans <eat ? eat : ans;
	}
}