[JAVA]19236 청소년 상어, 골드2 시뮬레이션

 📚 문제  

19236번: 청소년 상어

🔍 아이디어  

시뮬레이션 문제입니다. 삼성의 시뮬레이션 문제는 문제를 잘 읽고 문제에 적힌 순서 그대로 코드를 짜는 것이 중요한 것 같습니다.

이를 위해서 먼저 이동해야할 물고리를 모두 식별하고, 해당 물고리를 index순으로 정렬 후에 이동시킵니다. 

이동 후에는 상어가 움직입니다. 여기서 상어가 먹을 수 있는 모든 물고리에 대해서 DFS를 진행합니다. 

 

(물고기가 현재 이동 방향으로 이동할 수 없다면 반시계방향으로 45도 회전한다.) -> 저는 이 부분을 돌리기만 하고 물고기의 방향을 바꾸지 않아서 에러를 잡느라 시간이 좀 걸렸습니댜.. ㅠㅜㅠ

 

📝 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class boj_19236_청소년상어 {
    private static final int[][] dirs = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};
    private static int maxScore = 0;

    private static class Fish {
        int index;
        int dirIndex;
        int x, y;

        public Fish(Fish fish) {
            this.index = fish.index;
            this.dirIndex = fish.dirIndex;
            this.x = fish.x;
            this.y = fish.y;
        }

        public Fish(int index, int dirIndex, int x, int y) {
            this.index = index;
            this.dirIndex = dirIndex;
            this.x = x;
            this.y = y;
        }

        public void set(int x, int y) { //깊은 복사를 위한 팩토리 메서드
            this.x = x;
            this.y = y;
        }
    }

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

        Fish[][] fishArr = new Fish[4][4];

        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
                int index = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken()) - 1;
                fishArr[i][j] = new Fish(index, dir, i, j);
            }
        }


        Fish fish = fishArr[0][0];
        fishArr[0][0] = null; //0,0물고기는 이미 먹혔기때문에
        dfs(fishArr, 0, 0, fish.index, fish.dirIndex);
        System.out.println(maxScore);
    }


    public static void dfs(Fish[][] fishArr, int sX, int sY, int score, int dir) { //물고기 위치, 상어x, 상어 y, 현재 점수, 현재 상어의 방향
        maxScore = Math.max(maxScore, score); 

        //이동할 물고기를 모두 체크한다.
        List<Fish> fishPoll = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (fishArr[i][j] != null) {
                    fishPoll.add(fishArr[i][j]);
                }
            }
        }

        // 물고기는 순서대로 움직이기에 물고기 번호순으로 정렬한다.
        fishPoll.sort(Comparator.comparingInt(o -> o.index)); 
        for (Fish fish : fishPoll) {
            int fX = fish.x;
            int fY = fish.y;
            int fD = fish.dirIndex;

            boolean find = false;
            int swapX = -1, swapY = -1;
            for (int i = fD; i < fD + 8 && !find; i++) { //8방위, 물고기 이동경로 선택 전까지
                int[] tempDir = dirs[i % 8];
                int mvX = fX + tempDir[0];
                int mvY = fY + tempDir[1];
                if (mvX < 0 || mvY < 0 || 4 <= mvY || 4 <= mvX) continue; //범위를 넘어감
                if (mvX == sX && mvY == sY) continue; //상어가 있다.

                find = true; //물고기가 이동할 방향을 찾았다면 
                swapX = mvX;
                swapY = mvY;
                fish.dirIndex = i % 8; //물고기 방향이 바뀜 //이걸 안해서 고생했습니다..
            }

            //물고기가 이동할 수 있는 방향을 찾는다 이동 시킨다.
            if (find) {
                if (fishArr[swapX][swapY] != null) { //두 물고기의 위치를 바꾼다.
                    Fish swappedFish = fishArr[swapX][swapY];
                    swappedFish.set(fX, fY);
                    fish.set(swapX, swapY);

                    fishArr[swapX][swapY] = fish;
                    fishArr[fX][fY] = swappedFish;

                } else {// 빈칸인 경우!
                    fish.set(swapX, swapY);
                    fishArr[swapX][swapY] = fish;
                    fishArr[fX][fY] = null;
                }
            }
        }

        //상어가 먹을 수 있는 물고기 마다 확인한다.
        int[] sharkDir = dirs[dir];
        while (true) {
            sX += sharkDir[0];
            sY += sharkDir[1];

            if (sX < 0 || sY < 0 || 4 <= sX || 4 <= sY) break;//범위를 벗어남
            if (fishArr[sX][sY] == null) continue; //빈칸이다.

            //해당 물고기를 먹는다면
            Fish eatenFish = fishArr[sX][sY];
            fishArr[sX][sY] = null;

            //클론된 배열을 보낸다(계속해서 물고기의 위치가 변화하기 때문에)
            dfs(cloneArr(fishArr), sX, sY, score + eatenFish.index, eatenFish.dirIndex);
            fishArr[sX][sY] = eatenFish;
        }

    }

    private static Fish[][] cloneArr(Fish[][] fishArr) {
        Fish[][] cloneArr = new Fish[4][4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                Fish fish = fishArr[i][j];
                if (fish != null)
                    cloneArr[i][j] = new Fish(fish); //깊은 복사를 진행해야 한다.
            }
        }
        return cloneArr;
    }
}