백준 19236번 : 청소년 상어

 문제

www.acmicpc.net/problem/19236

19236번: 청소년 상어

19236 청소년 상어

 

 구현 방법

 갈 수 있는 곳 까지 갔다가 다시 돌아와야 하기 때문에 dfs를 사용하여 풀어주었습니다.

순서는 물고기 먹기 -> 물고기 이동 -> 상어 이동 입니다.

 

좌표, 방향, 생존여부를 저장할 fish클래스를 생성하여 물고기 배열을 만들어 주었습니다. 4X4 고정 즉 물고기는 항상 16개이므로 크기는 17개로 만들어주었습니다. 상어가 (0,0) 좌표에 있는 물고기를 먹으면서 시작됩니다. 

 

해당 경우 마다 값이 계속 바뀌므로 원래의 맵, 물고기 배열이 바뀌지 않도록 맵과 물고기 배열을 복사하여 사용했습니다.

상어의 이동 경우는 총 3가지 1칸 이동, 2칸 이동, 3칸 이동 이므로 1부터 3까지 반복문을 돌려 해당 인덱스를 가려는 방향에 곱해주어 칸을 결정하였습니다.

해당 칸에 물고기를 먹고 물고기의 생존 여부는 false로 만들어준 뒤 물고기를 이동시킵니다.

 

물고기는 작은 물고기부터 움직이므로 1부터 16까지 반복문을 돌려 이동이 가능한지 판별을 해주었습니다. 물고기가 범위를 벗어나거나 상어가 있는 위치라면 45도 방향으로 바꿔주고 그게 아니라면 값을 바꿔주었습니다.  혹여나 물고기가 이미 먹혀 해당 위치에 아무것도 없을 수 있으므로 해당 조건을 추가해주었습니다.

 

물고기 이동 후 상어가 이동합니다. 상어가 범위를 벗어날 시에는 그동안 먹은 물고기 합의 최댓값을 구해주고 0일 때 (물고기가 없을 때)에는 그냥 지나가도록 해주었습니다. 만약 물고기를 먹을 수 있다면 dfs로 넘겨 반복해주었습니다. 

 

로직은 완벽하다고 생각했는데 계속 마지막 예제가 맞지 않아 정말.. 하나하나 디버깅 해 본 결과 초기화가 잘못되었음을 알았습니다.. dfs를 돌리고 return을 해주면 죽었던 물고기를 다시 살려놔야 하는데 그 딱 한 줄 코드를 빼먹어 몇 시간을 잡아먹었습니다..

 

 구현 코드

package BOJ.Gold;

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

public class BOJ19236_청소년상어 {
	static int MAX;	
	static fish[] fishes;
 	static int[][] arr, deltas = {{0, 0}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}}; 
 	
	static class fish {
		int r, c, d;
		boolean alive;

		public fish(int r, int c, int d, boolean alive) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
			this.alive = alive;
		}
	}
	
	static class par {
		fish shark;
		int ans, key;
		int[][] arr;
		fish[] fishes;
		public par(fish shark, int ans, int key, int[][] arr, fish[] fishes) {
			super();
			this.shark = shark;
			this.ans = ans;
			this.key = key;
			this.arr = arr;
			this.fishes = fishes;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		arr = new int[4][4];
		fishes = new fish[17];
		for (int r=0;r<4;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<4;c++) {
				int num = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());
				arr[r][c] = num;
				fishes[num] = new fish(r, c, d, true);
			}
		}
		MAX = Integer.MIN_VALUE;
		dfs(new par(fishes[arr[0][0]], 0, arr[0][0], arr, fishes));
		System.out.println(MAX);
	}
	
	static void dfs(par in) {
		int[][] temp = new int[4][4];
		for (int i=0;i<4;i++) { // 맵 복사
			for (int j=0;j<4;j++) {
				temp[i][j] = in.arr[i][j];
			}
		}
		
		fish[] f = new fish[17];
		for (int i=1;i<=16;i++) { // 물고기 복사
			f[i] = in.fishes[i];
		}
		
		temp[in.shark.r][in.shark.c] = -1; // 상어!!
		f[in.key].alive = false; // 물고기 죽여주기
		// 물고기 이동
		fishMove(temp, f);
		
		// 상어 이동
		for (int i=1;i<=3;i++) { 
			int nr = in.shark.r + deltas[in.shark.d][0]*i; // i칸 만큼 이동
			int nc = in.shark.c + deltas[in.shark.d][1]*i; // i칸 만큼 이동
			
			if (!isIn(nr, nc)) {
				MAX = Math.max(MAX, in.ans+in.key); // 물고기 합의 최댓값 구하기
				break;
			} else if (temp[nr][nc]==0) continue;
			else {
				temp[in.shark.r][in.shark.c] = 0; // 상어 이동 = 전에 있었던 자리 0으로 바꿔주기
				int next = temp[nr][nc]; // 다음 먹을 물고기
				dfs(new par(new fish(nr, nc, f[next].d, true), in.ans+in.key, next, temp, f));
				// 초기화!!!!!!!!!
				temp[nr][nc] = next;
				temp[in.shark.r][in.shark.c] = -1;
				f[next].alive = true; // 물고기 다시 살려주기
			} 
		}
		return;
	}
	
	static void fishMove(int[][] temp, fish[] f) {
		for (int i=1;i<=16;i++) {
			if (f[i].alive) {
				fish now = f[i];
				int d = f[i].d;
				while (true) {
					int nr = now.r + deltas[d][0];
					int nc = now.c + deltas[d][1];
					if (!isIn(nr, nc) || temp[nr][nc]==-1) d = (d%8)+1; // 방향 바꿔주기
					else if (isIn(nr, nc)){
						swap(now, nr, nc, i, d, temp, f);
						break;
					}
				}
			}
		}
	}
	
	static void swap(fish now, int nr, int nc, int i, int d, int[][] temp, fish[] f) {
		int tmp = temp[nr][nc]; // 바꿔줄 물고기 번호
		
		temp[nr][nc] = i; // 바꿔줄 물고기 좌표에 현재 좌표 넣어줌
		temp[now.r][now.c] = tmp; // 현재 물고기 좌표에 바꿔줄 물고기 좌표 넣어줌
		if (tmp!=0) f[tmp] = new fish(now.r, now.c, f[tmp].d, true); // 물고기가 없을 때
		f[i] = new fish(nr, nc, d, true); // 현재 물고기 추가
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<4 && nc>=0 && nc<4;
	}
}

 

정답!