[ 백준 / BOJ 19236 ] 청소년 상어 ( 자바 / JAVA )

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

19236번: 청소년 상어

문제 설명

---

• 4X4 크기의 공간이 있고, 크기가 1X1인 정사각형 칸으로 나누어져 있다.
• 한 칸에는 물고기 한 마리 존재.
• 각 물고기는 번호와 방향을 가지고 있다.
• 1 <= 번호 <= 16
• 방향 : $\uparrow, \nwarrow, \leftarrow, \swarrow, \downarrow, \searrow, \rightarrow, \nearrow$

진행 순서

---

1. 청소년 상어가 (0,0) 물고기를 먹고, 그 물고기의 방향을 가지고 공간에 들어감
2. 물고기 이동
   1) 번호가 작은 순으로
   2) 한 칸 이동 가능, 빈 칸과 물고기가 있는 칸으로 이동 가능

    1) 방향에 이동 가능한 칸이 있다면,
        1-1) 빈칸이라면, 그대로 이동
        1-2) 물고기가 있다면, 두 물고기 교체
    2) 이동 가능한 칸이 없다면 
        2-1) 가능한 칸이 나올 때까지 반시계 방향으로 45도 회전
        2-2) 그래도 없다면, 패스

3. 청소년 상어 이동
   1) 방향에 있는 칸으로 이동 가능, 한 번에 여러 칸 이동 가능
   2) 물고기가 없는 칸으로는 이동 불가능
   ✅ 물고기가 없는 칸을 지나갈 수는 있음 ‼️
   3) 이동이 더 이상 불가능하면 종료
4. 청소년 상어가 먹을 수 있는 물고기 번호의 최댓값 출력 ‼️

문제 풀이

---

Fish Class

• 물고기 정보
• 물고기 번호, 좌표, 방향, 살아있는지 여부

1) 시작

(0,0) 물고기를 먹고 자리 차지
sx = 0, sy = 0, sd = fishes[map[0][0]].dir, map[0][0] = -1
map[x][y] = -1; 은 상어를 나타냄

2) DFS

DFS(sx, sy, sd, eat)
청소년 상어가 이동할 수 있는 경우의 수에서 최댓값을 찾아야하므로 DFS 이용

최종 결과인 amountOfEating과 eat을 비교해 최댓값을 amountOfEating으로 저장
✅ 진행하기 이전의 상태에서 다른 상황을 확인해야하므로, 기존의 배열을 미리 임시로 저장
✅ Fish 배열 경우, Arrays.copyOf()를 사용했더니, 기존의 값들이 변경 됨 → for문을 돌면서 새로 new Fish()로 추가

물고기 이동, 상어 이동 이후, 원래의 배열들을 저장해놓은 임시의 배열값으로 다시 변경해준다 ‼️

2-1) 물고기 이동

moveFishes()

1. 16마리 물고기 돌면서, 죽어있으면 PASS
2. 살아있다면 👉
   1) 바라보는 방향으로 이동 가능한 지 확인

    1-1) 가능하고, 물고기 없다면 👉 그대로 이동
    1-2) 가능하고, 다른 물고기가 있다면 👉 두 물고기 교체
    1-3) 가능하지 않다면, 반시계방향 45도 회전 👉 모든 방향이 불가하면 PASS

2-2) 상어 이동

moveShark(sx, sy, sd, eat)

1. 바라보는 방향으로 이동하는데,
   nx = sx + dx[sd] * i 로 i (1<=i<4)를 곱해줌으로써, 여러 칸 이동
2. map[nx][ny]에 물고기가 있다면, 물고기를 먹고 이동
3. 먹은 상태로 DFS(nx, ny, nd, eat + eatFish) 호출
4. 그 후, 안먹은 상태로 되돌린다.

코드

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

public class Main_BOJ_19236_청소년_상어 {

    static class Fish{
        int num, x, y, dir;
        boolean alive;

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

    static int[][] map;
    static Fish[] fishes;
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
    static int amountOfEating = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

        map = new int[4][4];
        fishes = new Fish[17];
        for (int i = 0; i < 4; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
                int num = Integer.parseInt(stringTokenizer.nextToken());
                int dir = Integer.parseInt(stringTokenizer.nextToken()) - 1;

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

        int sx = 0, sy = 0;
        int sd = fishes[map[0][0]].dir;
        int eat = map[0][0];
        fishes[map[0][0]].alive = false;
        map[0][0] = -1;

        DFS(sx, sy, sd, eat);

        System.out.println(amountOfEating);
    }

    private static void DFS(int sx, int sy, int sd, int eat) {
        amountOfEating = Math.max(amountOfEating, eat);

        int[][] tmpMap = new int[4][4];
        for (int i = 0; i < 4; i++) {
//            System.arraycopy(map[i], 0, tmpMap[i], 0, map.length);
            tmpMap[i] = Arrays.copyOf(map[i], 4);
        }

        Fish[] tmpFishes = new Fish[17];
        for (int i = 1; i < 17; i++) {
            tmpFishes[i] = new Fish(fishes[i].num, fishes[i].x, fishes[i].y, fishes[i].dir, fishes[i].alive);
        }

        moveFishes();
        moveShark(sx, sy, sd, eat);

        for (int i = 0; i < 4; i++) {
//            System.arraycopy(tmpMap[i], 0, map[i], 0, 4);
            map[i] = Arrays.copyOf(tmpMap[i], 4);
        }

        for (int i = 1; i < 17; i++) {
            fishes[i] = new Fish(tmpFishes[i].num, tmpFishes[i].x, tmpFishes[i].y, tmpFishes[i].dir, tmpFishes[i].alive);
        }
    }

    private static void moveShark(int sx, int sy, int sd, int eat) {
        for (int i = 1; i < 4; i++) {
            int nx = sx + dx[sd] * i;
            int ny = sy + dy[sd] * i;

            if(nx < 0 || ny < 0 || 4 <= nx || 4 <= ny || map[nx][ny] == 0) continue;

            int eatFish = map[nx][ny];
            int nd = fishes[eatFish].dir;
            map[sx][sy] = 0;
            map[nx][ny] = -1;
            fishes[eatFish].alive = false;

            DFS(nx, ny, nd, eat + eatFish);

            fishes[eatFish].alive = true;
            map[sx][sy] = -1;
            map[nx][ny] = eatFish;
        }
    }

    private static void moveFishes() {
        for (int i = 1; i < 17; i++) {
            if(!fishes[i].alive) continue;

            int cnt = 0;
            int dir = fishes[i].dir;
            int nx = 0, ny = 0;

            while (cnt < 8) {
                nx = fishes[i].x + dx[dir];
                ny = fishes[i].y + dy[dir];

                if(nx < 0 || ny < 0 || 4 <= nx || 4 <= ny || map[nx][ny] == -1){
                    dir = (dir + 1) % 8;
                    fishes[i].dir = dir;
                    cnt += 1;
                    continue;
                }
                else if (map[nx][ny] == 0) {
                    map[fishes[i].x][fishes[i].y] = 0;
                    fishes[i].x = nx;
                    fishes[i].y = ny;
                    map[nx][ny] = i;
                } else {
                    int changeFish = fishes[map[nx][ny]].num;
                    fishes[changeFish].x = fishes[i].x;
                    fishes[changeFish].y = fishes[i].y;
                    map[fishes[changeFish].x][fishes[changeFish].y] = changeFish;

                    fishes[i].x = nx;
                    fishes[i].y = ny;
                    map[nx][ny] = i;
                }
                break;
            }
        }
    }
}