[백준] 19236. 청소년 상어 (Java)

 

문제

19236번: 청소년 상어

 

알고리즘

구현, 시뮬레이션, 백트래킹

 

풀이

 

각 칸의 물고기 번호를 저장할 2차원 배열과

물고기 번호에 해당하는 물고기들의 정보(좌표, 번호, 방향, 생존 여부)를 담을 1차원 배열을 선언한다.

board = new int[4][4];
fishList = new Fish[17];

fishList 배열을 통해 각 번호의 물고기가 어디 있는지 바로 접근할 수 있다.

 

큰 틀은 다음과 같다.

 

1. (0,0) 의 물고기를 잡아먹고, [상어의 좌표, 먹은 물고기 번호 합, 방향]을 매개변수로 하는 dfs 함수를 호출한다.

 

dfs 함수 내부

2. 먹은 물고기 번호 합과 최댓값을 비교, 갱신한다.

3. 물고기들을 번호순으로 이동시킨다.

4. 상어를 이동시키고 물고기를 잡아먹은 후 해당 정보를 추가해 dfs 함수를 재귀 호출한다.

 

1. (0,0) 의 물고기를 잡아먹고, [상어의 좌표, 먹은 물고기 번호 합, 방향]을 매개변수로 하는 dfs 함수를 호출한다.

max = fishList[board[0][0]].v;
int sharkV = fishList[board[0][0]].v;
int sharkD = fishList[board[0][0]].d;
fishList[board[0][0]].alive = false;

dfs(0, 0, sharkV, sharkD);

이때, 잡아먹힌 물고기의 alive를 false로 바꿔준다.

 

dfs 내부

static void dfs(int sharkY, int sharkX, int sharkV, int sharkD) {

	// 최댓값 비교
	max = Math.max(max, sharkV);

	// 맵, 물고기 리스트 복사
    	...
		
	// 물고기 이동
	for (int i = 1; i <= 16; i++) {
    	...
	}
		
	// 상어 이동
	for (int i = 1; i <= 3; i++) {
        	// 해당 좌표의 물고기가 살아있다면 잡아먹고 재귀 호출한 후 다시 살리기
		if (target.alive) {
			target.alive = false;
			dfs(ny,nx, sharkV + target.v, target.d);		
			fishList[board[ny][nx]].alive = true;				
		}
	}

	// 맵, 물고기 리스트 복원
    	...
}

 

2. 먹은 물고기 번호 합과 최댓값을 비교, 갱신한다.

max = Math.max(max, sharkV);

 

3. 물고기들을 번호순으로 이동시킨다.

만약 해당 번호의 물고기가 죽었다면 이동할 수 없으므로 다음 물고기로 넘어간다.

팔방 탐색을 진행하며 이동할 수 있는 좌표라면 방향을 바꾸고 fishList와 board의 각 값을 교환한다.

// 물고기 이동
for (int i = 1; i <= 16; i++) {
	if (!fishList[i].alive) continue;

	Fish cur = fishList[i];

	// 이동할 수 있는 칸을 향할 때까지 45도 반시계 회전
	for (int d = 0; d <= 8; d++) {
		int nd = (cur.d + d - 1) % 8 + 1;
		int ny = cur.y + dy[nd];
		int nx = cur.x + dx[nd];

		if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4) continue;
		if (ny == sharkY && nx == sharkX) continue;

		// 위치 교환
		Fish target = fishList[board[ny][nx]];
		cur.d = nd;

		int tmp = board[ny][nx];
		board[ny][nx] = board[cur.y][cur.x];
		board[cur.y][cur.x] = tmp;
				
		int tmpY = cur.y;
		int tmpX = cur.x;
		cur.y = ny;
		cur.x = nx;
		target.y = tmpY;
		target.x = tmpX;
				
				
		break;
	}
}

 

4. 상어를 이동시키고 물고기를 잡아먹은 후 해당 정보를 추가해 dfs 함수를 재귀 호출한다.

상어를 1칸~3칸 이동시켰을 때 해당 좌표의 물고기를 먹을 수 있다면 잡아먹고 dfs를 재귀호출한다.

* dfs 호출이 반환되면 잡아먹은 물고기를 다시 살려야한다.

// 상어 이동
for (int i = 1; i <= 3; i++) {
	int ny = sharkY + dy[sharkD] * i;
	int nx = sharkX + dx[sharkD] * i;

	if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4)
		continue;

	Fish target = fishList[board[ny][nx]];
			
	if (target.alive) {
		target.alive = false;
		dfs(ny,nx, sharkV + target.v, target.d);				
		fishList[board[ny][nx]].alive =true;
	}
}

 

* 맵과 물고기 리스트를 복사해두었다가 dfs 호출이 반환되면 복원해주어야한다.

// 맵, 물고기 리스트 복사
int[][] copyBoard = new int[4][4];
for(int i=0; i<4; i++) {
	for(int j=0; j<4; j++) {
		copyBoard[i][j] = board[i][j];
	}
} 
		
Fish[] copyFishList = new Fish[17];
for(int i=1; i<17; i++) {
	Fish f = fishList[i];
	copyFishList[i] = new Fish(f.y, f.x, f.v, f.d, f.alive);
}

// 맵, 물고기 리스트 복원
board = copyBoard;
fishList = copyFishList;

* 복원 시 배열의 값을 일일이 변경한 것이 아니라 가르키는 객체를 변경했기 때문에

물고기를 되살릴 때 target.alive = true 가 아닌 fishList[board[ny][nx]].alive = true 로 작성해야한다.

 

배열의 값을 복사했던 것처럼 일일이 변경했다면 target.alive = true로 변경해도 상관없다.

 

코드

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

public class Main {
	static int[] dy = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] dx = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
	static int sharkIndex, max;
	static Fish[] fishList;
	static int[][] board;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		board = new int[4][4];
		fishList = new Fish[17];

		for (int i = 0; i < 4; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 4; j++) {
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				board[i][j] = a;
				fishList[a] = new Fish(i, j, a, b, true);
			}
		}

		max = fishList[board[0][0]].v;
		int sharkV = fishList[board[0][0]].v;
		int sharkD = fishList[board[0][0]].d;
		fishList[board[0][0]].alive = false;

		dfs(0, 0, sharkV, sharkD);

		System.out.println(max);
	}

	static void dfs(int sharkY, int sharkX, int sharkV, int sharkD) {

		max = Math.max(max, sharkV);

		// 맵, 물고기 리스트 복사
		int[][] copyBoard = new int[4][4];
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				copyBoard[i][j] = board[i][j];
			}
		} 
		
		Fish[] copyFishList = new Fish[17];
		for(int i=1; i<17; i++) {
			Fish f = fishList[i];
			copyFishList[i] = new Fish(f.y, f.x, f.v, f.d, f.alive);
		}
		
		
		// 물고기 이동
		for (int i = 1; i <= 16; i++) {
			if (!fishList[i].alive) continue;

			Fish cur = fishList[i];

			// 이동할 수 있는 칸을 향할 때까지 45도 반시계 회전
			for (int d = 0; d <= 8; d++) {
				int nd = (cur.d + d - 1) % 8 + 1;
				int ny = cur.y + dy[nd];
				int nx = cur.x + dx[nd];

				if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4)
					continue;
				
				if (ny == sharkY && nx == sharkX)
					continue;

				// 위치 교환
				Fish target = fishList[board[ny][nx]];
				cur.d = nd;

				int tmp = board[ny][nx];
				board[ny][nx] = board[cur.y][cur.x];
				board[cur.y][cur.x] = tmp;
				
				int tmpY = cur.y;
				int tmpX = cur.x;
				cur.y = ny;
				cur.x = nx;
				target.y = tmpY;
				target.x = tmpX;
				
				break;
			}
		}
		
		// 상어 이동
		for (int i = 1; i <= 3; i++) {
			int ny = sharkY + dy[sharkD] * i;
			int nx = sharkX + dx[sharkD] * i;

			if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4)
				continue;

			Fish target = fishList[board[ny][nx]];
			
			if (target.alive) {
				target.alive = false;

				dfs(ny,nx, sharkV + target.v, target.d);				
				fishList[board[ny][nx]].alive =true;
			}

		}

		// 맵, 물고기 리스트 복원
		board = copyBoard;
		fishList = copyFishList;
	}
	
	static class Fish {
		int y, x, v, d;
		boolean alive;

		public Fish(int y, int x, int v, int d, boolean alive) {
			this.y = y;
			this.x = x;
			this.v = v;
			this.d = d;
			this.alive = alive;
		}
	}
}