오늘 풀어본 문제는
백준 19236번 청소년 상어 입니다.

📕 문제 링크

❗️코드

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

class Fish
{
    int x,y,dir;
    boolean isLive;

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


}
public class Main {
    static int answer;
    static int [] dx = {0,-1,-1,0,1,1,1,0,-1}; // 0번인덱스 제외
    static int [] dy = {0,0,-1,-1,-1,0,1,1,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int [][] map = new int[4][4];
        Fish [] fishes = new Fish[17];

        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());
                int dir = Integer.parseInt(st.nextToken());

                map[i][j] = num;
                fishes[num] = new Fish(i,j,dir,true);
            }
        }

        eat(0,0,fishes[map[0][0]].dir,0,map,fishes);
        System.out.print(answer);
    }

    static void eat(int x, int y,int dir,int eatCnt,int [][] map,Fish [] fishes)
    {
        eatCnt += map[x][y];
        fishes[map[x][y]].isLive = false;
        dir = fishes[map[x][y]].dir;
        map[x][y] = 0;

        if(eatCnt > answer) answer = eatCnt;
        moveFish(map,fishes,x,y);

        int mx = x,my = y;
        for(int idx = 0; idx < 3; ++idx)
        {
            mx += dx[dir];
            my += dy[dir];

            if(!isValid(mx,my)) break;
            if(map[mx][my] > 0)
            {
                int [][] copyMap = new int[4][4];
                for(int i = 0; i < 4; ++i)
                {
                    System.arraycopy(map[i],0,copyMap[i],0,4);
                }
                Fish [] copyFishes = new Fish[17];
                for(int i = 1; i < fishes.length; ++i)
                {
                    copyFishes[i] = new Fish(fishes[i].x,fishes[i].y,fishes[i].dir,fishes[i].isLive);
                }
                eat(mx,my,dir,eatCnt,copyMap,copyFishes);
            }
        }
    }
    static void moveFish(int [][] map, Fish [] fishes,int sharkX,int sharkY)
    {
        nextFish : for(int i = 1; i < fishes.length; ++i)
        {
            Fish cur = fishes[i];
            if(cur.isLive)
            {
                int cnt = 8;
                while(cnt-- > 0)
                {
                    if(cur.dir > 8) cur.dir = 1;
                    int mx = cur.x + dx[cur.dir];
                    int my = cur.y + dy[cur.dir];

                    if(!isValid(mx,my) || (sharkX == mx && sharkY == my))
                    {
                        cur.dir++;
                        continue;
                    }
                    if(map[mx][my] > 0)
                    {
                        swap(map,fishes,cur,fishes[map[mx][my]]);
                        continue nextFish;
                    }
                    else
                    {
                        map[mx][my] = map[cur.x][cur.y];
                        fishes[map[cur.x][cur.y]] = new Fish(mx,my,cur.dir,true);
                        map[cur.x][cur.y] = 0;
                        continue  nextFish;
                    }
                }
            }
        }
    }
    static void swap(int [][] map, Fish [] fishes, Fish o1, Fish o2)
    {
        int tmp = map[o1.x][o1.y];
        map[o1.x][o1.y] = map[o2.x][o2.y];
        map[o2.x][o2.y] = tmp;

        fishes[map[o2.x][o2.y]] = new Fish(o2.x,o2.y,o1.dir,true);
        fishes[map[o1.x][o1.y]] = new Fish(o1.x,o1.y,o2.dir,true);


    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < 4 && y < 4;
    }

}

📝 풀이

최댓값을 알아내기 위해 모든 경우를 탐색해야하는 백트래킹 문제입니다.
상어가 물고기를 잡아먹을 수 있는 경우가 여러개 이므로 map 자체를 변경할 수 없었고,
함수 인자로 넘겨주게 되면 주솟값을 넘겨주어 원본이 변경되므로 재귀호출 이전에 map과 fishes 배열을 복사하여 넘겨주는 방식을 택했습니다.

📜 후기

앞서 푼 문제도 같은 골드2였는데 체감상 이게 훨~~~씬 어려웠네요 ㅎㅎ..
아기상어 후속편인가 싶어서 귀엽길래 풀었는데ㅋㅋㅋㅋㅋ몇시간을 붙잡았는지.....ㅠㅠ
가끔 이렇게 특히 헷갈리는 문제들이 있는데... 얼른 보완해야겠습니다ㅜ