[백준 19236번] 청소년 상어

문제 링크: 19236번 청소년 상어

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

 

어쩌면 쉬운 문제인데, 나는 구현에서 상당한 어려움을 느꼈다. 다음 두 항목을 참고하면 빨리 풀릴 듯하다...

 

1. 상태공간트리를 DFS 방식으로 탐색할 경우, 함수 진입 후에 조건을 확인한다.

2. 백트래킹에서 원래 상태로 되돌리는 것이 어려울 경우, 이전의 상태를 아예 저장해서 복원시킬 수도 있다.

3. map에는 물고기의 번호만, arr에는 물고기 번호에 해당하는 인덱스에 물고기 객체를 저장한다.

 

1, 2번은 일반적인 구현 과정에서의 문제이다. 특히 1번의 경우, 별 생각없이 함수 진입 이전에 조건을 확인하니 return 값을 결정하는 데 있어서 굉장한 어려움을 겪었다.

3번은 자료구조를 어떻게 사용하느냐의 문제일 것이다. 처음에는 map에도 각 객체를 저장했는데, 물고기들 또한 row, col을 가지고 있기에 구현이 굉장히 복잡해졌다. 하지만 잘 생각해보면 물고기 클래스가 물고기 번호를 저장하고 있을 필요가 없었다.

 

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

class Fish {
    int row;
    int col;
    int dir;
    boolean isAlive;

    Fish(int row, int col, int dir, boolean isAlive) {
        this.row = row; this.col = col; this.dir = dir; this.isAlive = isAlive;
    }

    Fish() {
        new Fish(0, 0, 0, true);
    }
}

public class Main {
    static int[] drow = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dcol = {0, -1, -1, -1, 0, 1, 1, 1};

    static void swapFish(Fish f1, Fish f2, int[][] map) { // row, col 바꾸고 map 정보 바꾸어줌
        int temp;
        temp = map[f1.row][f1.col];
        map[f1.row][f1.col] = map[f2.row][f2.col];
        map[f2.row][f2.col] = temp;
        temp = f1.row;
        f1.row = f2.row;
        f2.row = temp;
        temp = f1.col;
        f1.col = f2.col;
        f2.col = temp;
    }

    static Fish findFish(int val, Fish[] arr) {
        return arr[val];
    }

    static Fish[] copyArr(Fish[] arr) {
        Fish[] res = new Fish[arr.length];
        for (int i = 0; i < arr.length; i++) {
            Fish f = arr[i];
            res[i] = new Fish(f.row, f.col, f.dir, f.isAlive);
        }
        return res;
    }

    static int[][] copyMap(int[][] map) {
        int[][] res = new int[4][4];
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                res[i][j] = map[i][j];
        return res;
    }

    static int solution(int sharkRow, int sharkCol, int sharkEatSum, Fish[] arr, int[][] map) {
        // 현재 상어의 위치가 (sharkRow, sharkCol)이 되고자 하고, 현재까지 점수가 sharkDir, sharkEatSum일 때, 최대의 합을 반환

        if (sharkRow<0||sharkCol<0||sharkRow>3||sharkCol>3)
            return sharkEatSum;
        if (!findFish(map[sharkRow][sharkCol], arr).isAlive)
            return sharkEatSum;
        
        // (sharkRow, sharkCol)이 상어가 올 수 있는 위치라면
        int feedId = map[sharkRow][sharkCol];
        sharkEatSum += feedId; // 상어 점수 갱신
        Fish feed = findFish(feedId, arr);
        int sharkDir = feed.dir; // 상어 방향 갱신
        feed.isAlive = false; // 물고기 생존 여부 갱신

        /* 물고기 이동 */
        for (Fish f : arr) {
            // 죽은 물고기는 움직이지 않는다...
            if (!f.isAlive)
                continue;

            // 움직일 수 있는 물고기라면...
            int oriDir = f.dir;
            for (int turn = 0; turn < 8; turn++) {
                f.dir = (oriDir+turn) % 8;
                int nrow = f.row + drow[f.dir];
                int ncol = f.col + dcol[f.dir];

                // 공간을 벗어나면 회전
                if (nrow<0||ncol<0||nrow>3||ncol>3)
                    continue;

                // 상어를 만나면 회전
                if (nrow == sharkRow && ncol == sharkCol)
                    continue;

                // 이동할 수 있는 칸이면
                Fish targetPosFish = findFish(map[nrow][ncol], arr);
                swapFish(f, targetPosFish, map);
                break;
            }
        }

        /* 상어 이동 */
        int max = 0;
        for (int dist = 1; dist <= 3; dist++) {
            Fish[] arr2 = copyArr(arr);
            int[][] map2 = copyMap(map);

            int nrow = sharkRow + dist*drow[sharkDir];
            int ncol = sharkCol + dist*dcol[sharkDir];

            int res = solution(nrow, ncol, sharkEatSum, arr2, map2);
            if (res > max)
                max = res;
        }

        return max;
    }

    public static void main(String[] args) throws IOException {
        Fish[] arr = new Fish[17]; // 물고기 정보를 저장, 물고기 번호가 인덱스
        int[][] map = new int[4][4]; // 물고기 번호를 저장

        /* input start */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr[0] = new Fish();
        for (int l = 0; l < 4; l++) {
            int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int t = 0; t < 8; t += 2) {
                int id = line[t];
                int dir = line[t+1]-1;
                arr[id] = new Fish(l, t/2, dir, true);
                map[l][t/2] = id;
            }
        }
        /* input end */

        int res = solution(0, 0, 0, arr, map);

        System.out.println(res);
    }
}