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

문제 설명

아기 상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

풀이 방법

• 시뮬레이션 + 백트레킹 문제이다.
• 먼저 시뮬레이션 순서를 보면 상어가 먹는다 -> 물고기가 회전한다. -> 상어가 먹이를 찾는다(백트래킹)
• 상어가 먹이를 찾을 때 백트래킹을 쓰는 이유는 먹은 마리 수의 최대값을 구하기 위해서이다. 백트래킹을 사용했을 때 (3^16)으로 시간복잡도는 충분하다.
• 백트래킹을 사용하기 위해선 상태를 저장해놓는 변수가 필요하다. 최적의 해가 아니면 다시 돌아가야하기 때문이다. 이를 위해 dfs 내부에 배열을 복사하여 최적의 해를 구했다.(핵심 포인트)
• 시뮬레이션과 백트래킹을 연계한 문제여서 신선했다. 

알아야되는 개념

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

import java.util.*;
import java.io.*;
public class Main {
    static int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1 };
    static int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};
    static int ans;
    static class info{
        int x,y,dir;
        info(int x, int y, int dir){
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }
    static void dfs(info Fish[], int mat[][], int shark_x, int shark_y ,int sum){
        //copy
        info temp_Fish[] = new info[16];
        int temp_mat[][] = new int[4][4];
        for(int i=0;i<16;i++){
            temp_Fish[i] = new info(Fish[i].x, Fish[i].y, Fish[i].dir); // warring
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                temp_mat[i][j] = mat[i][j];
            }
        }
        //eat
        int fish_number = temp_mat[shark_x][shark_y];
        int shark_dir = temp_Fish[fish_number].dir;
        temp_Fish[fish_number].x = -1;
        temp_Fish[fish_number].y = -1;
        temp_Fish[fish_number].dir = -1;
        temp_mat[shark_x][shark_y] = -1;

        sum += (fish_number + 1);
        if(sum > ans)
            ans = sum;

        //fish move
        for(int i=0;i<16;i++){
            if(temp_Fish[i].x == -1) continue;
                int x = temp_Fish[i].x;
                int y = temp_Fish[i].y;
                int d = temp_Fish[i].dir;
                int nx = x + dx[d];
                int ny = y + dy[d];
                int nd = d;
                 while (ny < 0 || ny >= 4 || nx < 0 || nx >= 4 || (ny == shark_y && nx == shark_x)) {
                    nd = (nd + 1) % 8;
                    ny = y + dy[nd];
                    nx = x + dx[nd];
                 }

                if (temp_mat[nx][ny] != -1){  //swap 해야함
                    int target = temp_mat[nx][ny];
                    temp_Fish[target].x = x;
                    temp_Fish[target].y = y;

                    temp_Fish[i].x = nx;
                    temp_Fish[i].y  = ny;
                    temp_Fish[i].dir = nd;

                    temp_mat[x][y] = target;
                    temp_mat[nx][ny] = i;
                }
                else{
                    temp_Fish[i].x = nx;
                    temp_Fish[i].y  = ny;
                    temp_Fish[i].dir = nd;

                    temp_mat[x][y] = -1;
                    temp_mat[nx][ny] = i;
                }

            }

        for(int i=1;i<4;i++){
            int x = shark_x + dx[shark_dir]  * i;
            int y = shark_y + dy[shark_dir]  * i;
            if(x>=4 || x< 0 || y>=4 || y<0) break;
            if(temp_mat[x][y] != -1){
                dfs(temp_Fish, temp_mat, x, y, sum);
            }
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        info Fish[] = new info[16];
        int mat[][] = new int[4][4];
        int sum = 0;
        for(int i=0;i<4;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<4;j++){
                int a = Integer.parseInt(st.nextToken());  //val
                int b = Integer.parseInt(st.nextToken());  //dir
                Fish[a - 1] = new info(i, j, b - 1);
                mat[i][j] = a - 1;
            }
        }
        dfs(Fish, mat, 0,0,0);
        System.out.println(ans);
    }
}