[Java] 백준 19236번 청소년 상어

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구하는 문제입니다.
상어는 0,0에서 시작하며 해당 물고기의 점수와 방향을 가지고 시작합니다.

해당하는 방향으로 공백이 아닌 곳은 이동 할 수 있습니다.
예제 1의 경우 처음 (0,0)에서 오른쪽 대각선 방향이므로 (1,1)  (2,2)  (3,3) 3곳을 갈 수 있습니다.
DFS탐색으로 갈 수 있는 위치를 전부 접근해서 모든 가능한 곳을 탐색해줍니다.
한번 탐색할 때마다 물고기들의 움직임을 함수로 주어서 실행해 주었습니다.

물고기는 1번부터 16번까지 중복되지 않는 수로 이루어지며 번호가 작은 순서로 차례대로 움직입니다.
상어가 있는 위치는 접근을 하지 못하며, 4*4 밖으로 나갈 수 없도록 설정해주었습니다.

import java.util.Scanner;

public class Main {
	static int ans = 0;  
  static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
  static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[][] map = new int[4][4];
		int[][] dir = new int[4][4];
		int[] orderY = new int[16];
		int[] orderX = new int[16];		
		for(int i=0; i<4; ++i) {
			for(int j=0; j<4; ++j) {
				map[i][j] = sc.nextInt();
				orderY[map[i][j] - 1] = i;
				orderX[map[i][j] - 1] = j;
				dir[i][j] = sc.nextInt() - 1;
			}
		}
		dfs(0, 0, map, dir, 0, orderY, orderX);		
		
		System.out.println(ans);
	}	
	public static void dfs(int y, int x, int[][] map, int[][] dir, int sum, int[] orderY, int[] orderX) {
		int nextY = y;
		int nextX = x;
		int[][] newMap = new int[4][4];
		int[][] newDir = new int[4][4];		
		int[] newOrderY = new int[16];
		int[] newOrderX = new int[16];
		for(int i=0; i<4; ++i) {
			for(int j=0; j<4; ++j) {
				newMap[i][j] = map[i][j];
				newDir[i][j] = dir[i][j];
				newOrderY[i*4+j] = orderY[i*4+j];
				newOrderX[i*4+j] = orderX[i*4+j];
			}
		}
		sum += newMap[y][x];
		newOrderY[newMap[y][x] - 1] = -1;
		newOrderX[newMap[y][x] - 1] = -1;
		newMap[y][x] = -1;
		move(y, x, newMap, newDir, newOrderY, newOrderX);
		newMap[y][x] = 0;
		while(true) {
			nextY += dy[newDir[y][x]];
			nextX += dx[newDir[y][x]];
			if(nextY < 0 || nextX < 0 || nextY >= 4 || nextX >= 4) {
				break;
			}
			if(newMap[nextY][nextX] == 0) {
				continue;
			}
			dfs(nextY, nextX, newMap, newDir, sum, newOrderY, newOrderX);
		}
		ans = Math.max(ans, sum);
	}
	public static void move(int y, int x, int[][] map, int[][] dir, int[] orderY, int[] orderX) {
		int oy, ox;
		int noy, nox;
		int tmp;
		for(int i=0; i<16; ++i) {
			oy = orderY[i];
			ox = orderX[i];
			if(orderY[i] < 0 || map[oy][ox] <= 0) {
				continue;
			}
			for(int j=0; j<8; ++j) {
				noy = oy + dy[(dir[oy][ox] + j) % 8];
				nox = ox + dx[(dir[oy][ox] + j) % 8];
				if(noy < 0 || nox < 0 || noy >= 4 || nox >= 4) {
					continue;
				}
				if(map[noy][nox] == -1) {
					continue;
				}
				orderY[i] = noy;
				orderX[i] = nox;
				if(map[noy][nox] > 0) {
					orderY[map[noy][nox] - 1] = oy;
					orderX[map[noy][nox] - 1] = ox;
				}
				tmp = map[noy][nox];
				map[noy][nox] = map[oy][ox];
				map[oy][ox] = tmp;
				tmp = dir[noy][nox];
				dir[noy][nox] = (dir[oy][ox] + j) % 8;
				dir[oy][ox] = tmp;
				break;
			}
		}
	}
}