[BOJ - Java] 19236번 청소년 상어

 

문제

---

 

19236번 - 청소년 상어 : https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

 

 

정답 및 풀이

---

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

public class Main {
    private static class Shark {
        int dir, sum, x, y;

        Shark(int dir, int sum, int x, int y) {
            this.dir = dir;
            this.sum = sum;
            this.x = x;
            this.y = y;
        }
    }

    private static class Fish implements Comparable<Fish> {
        int id, dir, x, y;
        boolean alive = true;

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

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

        @Override
        public int compareTo(Fish o) {
            return Integer.compare(id, o.id);
        }
    }

    private static final int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    private static final int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
    private static int max = 0;

    private final static int FISHBOWL_SIZE = 4;
    private final static int DIRECT_SIZE = dx.length;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[][] arr = new int[FISHBOWL_SIZE][FISHBOWL_SIZE];
        List<Fish> fishList = new ArrayList<>();

        for (int i = 0; i < FISHBOWL_SIZE; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < FISHBOWL_SIZE; j++) {
                int id = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken()) - 1;
                Fish f = new Fish(id, dir, i, j);

                fishList.add(f);
                arr[i][j] = f.id;
            }
        }

        Collections.sort(fishList);

        Fish f = fishList.get(arr[0][0] - 1);
        Shark shark = new Shark(f.dir, f.id, 0, 0);
        f.alive = false;
        arr[0][0] = -1;

        dfs(arr, fishList, shark);

        bw.write(Integer.toString(max));
        bw.close();
    }

    private static void dfs(int[][] arr, List<Fish> fishList, Shark shark) {
        max = Math.max(max, shark.sum);

        for (Fish f : fishList) {
            move(f, arr, fishList);
        }

        for (int dist = 1; dist < 4; dist++) {
            int xx = shark.x + dx[shark.dir] * dist;
            int yy = shark.y + dy[shark.dir] * dist;

            if (check(xx, yy) && arr[xx][yy] > 0) {
                int[][] arrCopies = copyArr(arr);
                List<Fish> fishCopyList = copyList(fishList);

                arrCopies[shark.x][shark.y] = 0;
                Fish f = fishCopyList.get(arr[xx][yy] - 1);
                Shark newShark = new Shark(f.dir, shark.sum + f.id, f.x, f.y);
                f.alive = false;
                arrCopies[f.x][f.y] = -1;

                dfs(arrCopies, fishCopyList, newShark);
            }
        }
    }

    private static boolean check(int x, int y) {
        return 0 <= x && x < FISHBOWL_SIZE && 0 <= y && y < FISHBOWL_SIZE;
    }

    private static void move(Fish fish, int[][] arr, List<Fish> fishList) {
        if (!fish.alive) return;

        for (int i = 0; i < DIRECT_SIZE; i++) {
            int nextDir = (fish.dir + i) % DIRECT_SIZE;
            int xx = fish.x + dx[nextDir];
            int yy = fish.y + dy[nextDir];

            if (check(xx, yy) && arr[xx][yy] > -1) {
                arr[fish.x][fish.y] = 0;

                if (arr[xx][yy] != 0) {
                    Fish temp = fishList.get(arr[xx][yy] - 1);
                    temp.x = fish.x;
                    temp.y = fish.y;
                    arr[fish.x][fish.y] = temp.id;

                }
                fish.x = xx;
                fish.y = yy;

                arr[xx][yy] = fish.id;
                fish.dir = nextDir;
                return;
            }
        }
    }

    private static int[][] copyArr(int[][] arr) {
        int[][] copyArr = new int[FISHBOWL_SIZE][FISHBOWL_SIZE];

        for (int i = 0; i < FISHBOWL_SIZE; i++) {
            System.arraycopy(arr[i], 0, copyArr[i], 0, FISHBOWL_SIZE);
        }

        return copyArr;
    }

    private static List<Fish> copyList(List<Fish> fishList) {
        List<Fish> copyList = new ArrayList<>();
        for (Fish f : fishList) {
            copyList.add(new Fish(f.id, f.dir, f.x, f.y, f.alive));
        }
        return copyList;
    }
}