[BOJ] 19236. 청소년 상어

https://www.acmicpc.net/problem/19236

접근 방법

후.. 너무 힘들었다 3시간은 걸린거 같다.

DFS로 구현을 했었다.

1. 무조건 시작은 0,0 으로 시작을 한다.
2. 상어가 0,0을 먹고 시작하니 0,0의 방향을 가지고 먹을 것이 있나 탐색을 한다.
3. 먹을 것이 있으면 이제 재귀로 쭉 들어가본다.
4. 가야할 방향에 먹을 것이 더 이상 없다면 끝을 내고 결과값을 저장한다.(최대로)

주의 사항

1. 같은 맵을 쓰면 안된다. 재귀호출을 한번 다 돌리면 다시 돌려놔줘야한다.
2. 먹을 것이 없다는 것은 같은 방향으로 쭉 갔을 때 더 이상 존재하지 않는 것이다.

Need Know

1. DFS
2. 재귀 호출의 이해?
3. 깊은 복사와 얕은 복사의 차이
4. 그냥 시뮬레이션..

전체 코드 ( Java )

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
    static int[][] map = new int[4][4];
    static Fish[] fish = new Fish[17];
    static int ans =0;
    public static void main(String[] args) throws IOException {
        set();
        solve();
        bw.flush();
        bw.close();
        br.close();
    }
    static void set() throws IOException {
        for(int i=0; i<4; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int k=0; k<4; k++){
                int number = Integer.parseInt(st.nextToken());
                int direction = Integer.parseInt(st.nextToken())-1;
                map[i][k] = number;
                fish[number] = new Fish(i,k,direction,1);
            }
        }
    }
    static void solve() throws IOException {
        int first_eat = map[0][0];
        map[0][0] = -1;
        fish[first_eat].state = 0;  // 물고기가 죽어버림

        dfs(0,0,fish[first_eat].dir,first_eat);
        bw.write(ans+"");
    }
    static void dfs(int shark_x, int shark_y, int shark_direction ,int eat) {
        int[][] copyMap = new int[4][4];
        Fish[] copyFish = new Fish[17];

        for(int i=0;i<4; i++){
            copyMap[i] = map[i].clone();
        }
        copyFish = fish.clone();

        sort_map();
//        for(int i=0; i<4; i++){
//            for(int k=0; k<4; k++){
//                System.out.print(map[i][k] +" ");
//            }
//            System.out.println();
//        }
        for(int i=1;i<4; i++){
            int nx = shark_x + dx[shark_direction]*i;
            int ny = shark_y + dy[shark_direction]*i;
            if(nx<4 && ny<4 && nx>=0 && ny>=0) {
                if(map[nx][ny] ==0) continue;
                map[shark_x][shark_y] = 0;
                int eatable = map[nx][ny];
//                System.out.println(eatable);
                map[nx][ny] = -1;
                fish[eatable].state = 0;
                dfs(nx,ny,fish[eatable].dir,eat+eatable);
                map[nx][ny] = eatable;
                fish[eatable].state = 1;
                map[shark_x][shark_y] = -1;
            }else {
                break;
            }
        }
        for(int i=0; i<4; i++) {
            map[i] = copyMap[i].clone();
        }

        for(int i=1; i<=16; i++) {
            fish[i] = copyFish[i];
        }
        ans = Math.max(eat,ans);
    }
    static void sort_map(){
        for(int i=1; i<=16; i++){
            if(fish[i].state==0) continue;
            Fish now = fish[i];
            int x = now.x, y = now.y, dir = now.dir;
            for(int k=0; k<8; k++) {
                int nd = (dir+k)%8;
                int nx = x + dx[nd];
                int ny = y + dy[nd];
                if(nx>=4||ny>=4||nx<0||ny<0||map[nx][ny]==-1) continue;
                int fish_num = map[nx][ny];
                map[nx][ny] = map[x][y];
                map[x][y] = fish_num;
                fish[i] = new Fish(nx,ny,nd,1);
                // 물고기가 존재 한다면
                if(fish_num != 0){
                    fish[fish_num] = new Fish(x,y,fish[fish_num].dir,1);
                }
                break;
            }
        }
    }
}
class Fish{
    int x,y,dir,state;

    public Fish(int x, int y, int dir,int state) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.state = state;
    }
}