[BOJ 19236] 청소년상어

문제

• BOJ 19236
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

처음에 상어가 이동할 때 가장 큰 번호를 먹으면 되는줄 알았는데 작은 번호를 먹어도 이후에 더 큰 번호를 먹을 수 있기 때문에 갈 수 있는 모든 경우를 따져봐야 하는 문제이다. dfs(재귀 호출)를 사용하였음

1. 번호가 작은 순서대로 물고기를 이동시킨다.
   1. 물고기를 하나 꺼내서 이미 먹었는지 체크 후 8방향 탐색으로 다음 좌표를 구한다.
   2. 범위 체크, 비었거나 다른 물고기가 있는지 확인하고 이동시키기 위해 현재 좌표를 비워준다.
      1. 빈칸이면 다음 좌표로 이동시킨다.
      2. 다른 물고기가 있으면 두 물고기의 좌표를 바꿔준다. → 이때 map[][]과 fishArr[]배열 둘다 바꿔줘야 함에 유의
2. 상어를 이동시킨다.
   1. 상어가 최대 이동가능한 1~3거리만큼 다음 좌표를 구한다.
      1. 범위체크, 0보다 큰지 확인
      2. 이동가능하면 map[][], fishArr[]을 복사 후 물고기를 먹고 새로운 상어를 만들어서 go()를 재귀호출한다. → 원래 맵,배열,상어는 다음 거리를 가야하므로 보존해주기 위해 복사 후 넘겨줘야함 → 얕은 복사, 깊은 복사에 대한 개념 명확히 알아야 풀 수 있는 문제(배열이 아니라 리스트인 경우 Iterator을 사용하여 바로 복사가능)
3. go()에 재귀로 돌 때 마다 현재까지 먹은 물고기 합 sum이 최대일 때 Ans를 갱신해준다.

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static final int N = 4;
	static int[][] dArr = { { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }, { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 } }; //반시계방향
	static int Ans;
	
	static class Shark{
		int x, y, d, sum;
		
		public Shark(int x, int y, int d, int sum) {
			this.x = x;
			this.y = y;
			this.d = d;
			this.sum = sum;
		}
	}
	
	static class Fish {
		int num, x, y, d;
		boolean dead;

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

	public static void main(String[] args) throws IOException {
		int[][] map = new int[N][N];
		Fish[] fishArr = new Fish[N*N+1];
		
		for (int i = 0; i < 4; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < 4; j++) {
				int num = Integer.parseInt(st.nextToken()); //번호 0부터 시작
				int d = Integer.parseInt(st.nextToken()) - 1;//방향 0부터 시작
				fishArr[num] = new Fish(num, i, j, d, false);
				map[i][j] = num;
			}
		} // End input
		
		//초기 상어 세팅
		Fish f = fishArr[map[0][0]];
		Shark s = new Shark(0, 0, f.d, f.num);
		f.dead = true;
		map[0][0] = -1; //먹음 표시
		
		// 탐색 시작
		go(map, fishArr, s);
        System.out.println(Ans);
	}

	private static void go(int[][] map, Fish[] fishArr, Shark s) {
		//물고기 먹은 최대합을 답으로
		Ans = Math.max(Ans, s.sum);
		
		//1. 번호 작은 순서대로 물고기 이동
		for(int i=1; i<=N*N; i++) {
			Fish f = fishArr[i];
			if(f.dead) continue; //이미 먹은 물고기면 continue
			
			for(int d=0; d<8; d++) {
				int nd = (f.d + d) % 8;
				int nx = f.x + dArr[nd][0];
				int ny = f.y + dArr[nd][1];
				
				//범위 체크
				if(nx>=0 && nx<N && ny>=0 && ny<N && map[nx][ny] > -1) {
					map[f.x][f.y] = 0; //현재 있던 자리는 비워줌
					
					if(map[nx][ny] == 0) { //빈칸이면 이동
						f.x = nx;
						f.y = ny;
					}else { //물고기 있으면 위치 바꿈
						Fish tmp = fishArr[map[nx][ny]];
						tmp.x = f.x;
						tmp.y = f.y;
						map[f.x][f.y] = tmp.num;
						f.x = nx;
						f.y = ny;
					}
					
					map[nx][ny] = f.num;
					f.d = nd;
					break; //이동했으면 종료
				}
			}
		}
		
		//2. 상어 이동
		for(int dist = 1; dist < N; dist++){ //최대 이동가능거리 3
			int nx = s.x + dArr[s.d][0] * dist;
			int ny = s.y + dArr[s.d][1] * dist;
			
			//범위체크, 물고기 있으면 이동 가능
			if(nx>=0 && nx<N && ny>=0 && ny<N && map[nx][ny] > 0) {
				//배열 복사
				int[][] copyMap = copyMap(map);
				Fish[] copyFish = copyFish(fishArr);
				
				copyMap[s.x][s.y] = 0; //상어 있던곳 비움
				Fish f = copyFish[map[nx][ny]];
				Shark ns = new Shark(f.x, f.y, f.d, s.sum + f.num); //먹은 물고기 좌표,방향으로 상어상태 갱신
				f.dead = true;
				copyMap[f.x][f.y] = -1; //물고기 먹음
				go(copyMap, copyFish, ns);
			}
		}
	}

	private static Fish[] copyFish(Fish[] fishArr) {
		Fish[] tmp = new Fish[N*N+1];
		for(int i=1; i<=N*N; i++) {
			Fish f = fishArr[i];
			tmp[i] = new Fish(f.num, f.x, f.y, f.d, f.dead);
		}
		return tmp;
	}

	private static int[][] copyMap(int[][] map) {
		int[][] copy = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				copy[i][j] = map[i][j];
			}
		}
		
		return copy;
	}
}