백준 19236 청소년 상어 자바(java)

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

19236번: 청소년 상어

 

풀이 방법

백트래킹 알고리즘 자체는 쉽게 생각할 수 있었으나 구현이 까다로운 문제였다.

DFS + 백트래킹으로 상어가 이동할 수 있는 모든 경우에 대해 탐색하면서 먹은 물고기 번호의 최댓값을 구한다.

dfs 함수를 호출한 후 먼저 물고기를 모두 이동시키고 상어가 이동가능한 칸을 전부 확인하면서 각 경우에 dfs 함수를 재귀 호출하여 탐색한다. dfs 함수가 끝나면 다음 이동가능한 칸에 대해 새롭게 탐색하기 위해 이전에 탐색하면서 바뀐 상태를 다시 원래의 상태로 복구시켜야 하므로 상어를 이동시키기 전 상태를 복사해놓고 복사본을 이용해 복구시킨다.

 

주의할 점

문제에서 상어가 이동 시 '물고기가 없는 칸으로는 이동할 수 없다' 라는 말에 대한 해석이 헷갈릴 수 있다. 처음엔 이동할 칸에 물고기가 없으면 아예 지나갈 수도 없다고 생각하여 바로 탐색을 종료하는 것으로 풀어서 틀렸다. 이게 아니라 물고기가 없어도 칸을 지나갈 수 있으며 도착지, 즉 DFS 재귀 호출을 하는 시점이 되는 칸이 물고기가 있는 칸이어야 한다는 뜻이다. 따라서 현재 칸에 물고기가 없어도 그 다음 칸들 중 물고기가 있는 칸이 있을 수 있으므로 이어서 다음 칸에 대해 탐색을 진행해야 한다.

 

삽질했던 부분!

현재 상태를 복사하여 복사본을 만들 땐 깊은 복사를 잘 했으나 백트래킹 시 원래의 상태로 복구시킬 때 얕은 복사를 하고 있었다.. 얕은 복사는 주소가 복사되므로 다음 이동 가능한 칸 탐색할 때 원래의 상태가 바뀌면 복사본의 상태까지 바뀌어 복사본의 상태를 계속 유지할 수 없게 된다! (이게 예제로는 안잡히는 문제라 삽질을 꽤 했다....) 얕은 복사, 깊은 복사 주의하자!

 

코드

import java.io.*;

public class Main {

    public static class Fish {
        int x;
        int y;
        int d; // 방향
        boolean alive; // 생존 여부

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

    static int[][] board = new int[4][4];
    static Fish[] fishes = new Fish[17];
    static int answer = 0;
    static int[] dx = {0, -1, -1, 0, 1, 1, 1, 0, -1};
    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));
        for(int i=0; i<4; i++) {
            String[] line = br.readLine().split(" ");
            for(int j=0; j<8; j += 2) {
                int num = Integer.parseInt(line[j]); // 번호
                int direct = Integer.parseInt(line[j+1]); // 방향
                board[i][j / 2] = num;
                fishes[num] = new Fish(i, j/2, direct, true);
            }
        }

        // (0, 0) 에 있는 물고기 먹음
        int fNum = board[0][0];
        Fish fish = fishes[fNum];
        fish.alive = false;
        board[0][0] = -1;

        move(0, 0, fNum, fish.d);
        System.out.println(answer);
    }

    public static void move(int sx, int sy, int total, int d) {

        // 물고기 이동
        moveFish(sx, sy);
        
        // 상태 복구를 위한 복사
        int[][] temp = new int[4][4];
        Fish[] tempFishes = new Fish[17];
        copy(temp, tempFishes, board, fishes);

        int step = 1;
        while(true) {
            int nx = sx + dx[d] * step;
            int ny = sy + dy[d] * step;
            if(nx < 0 || nx >= 4 || ny < 0 || ny >= 4) { // 경계를 넘으면 이동 불가
                answer = Math.max(answer, total);
                break;
            }
            // 물고기가 없는 칸이면 건너뜀
            if(board[nx][ny] == -1) {
                step++;
                continue;
            }

            // 해당 칸으로 이동하여 물고기를 먹음
            int fNum = board[nx][ny];
            Fish target = fishes[fNum];
            target.alive = false;
            board[nx][ny] = -1;

            move(nx, ny, total + fNum, target.d);

            // 백트래킹
            copy(board, fishes, temp, tempFishes);
            step++; // 한 칸 더 이동
        }
    }

    public static void moveFish(int sx, int sy) {

        for(int i=1; i<=16; i++) {
            Fish fish = fishes[i];
            if(!fish.alive) { // 죽은 물고기인 경우
                continue;
            }

            boolean moved = false; // 이동 여부
            int curd = fish.d; // 현재 방향
            while(!moved) {
                int nx = fish.x + dx[curd];
                int ny = fish.y + dy[curd];
                // 경계를 벗어나거나 상어가 있으면 반시계 회전
                if((nx < 0 || nx >= 4 || ny < 0 || ny >= 4) || (sx == nx && sy == ny)) {
                    curd = (curd + 1 > 8) ? 1 : curd + 1; // 회전한 후의 방향
                    if(curd == fish.d) { // 처음 방향으로 돌아온 경우엔 탈출
                        break;
                    }
                    continue;
                }
                // 물고기 이동 -> 서로의 위치를 바꿈
                switchFish(nx, ny, fish.x, fish.y, board[nx][ny], i, curd);
                moved = true;
            }
        }
    }

    public static void switchFish(int nx, int ny, int x, int y, int num1, int num2, int direct) {
        // 이동할 곳에도 물고기가 있으면 옮겨줌
        if(num1 != -1) {
            fishes[num1].x = x;
            fishes[num1].y = y;
        }

        fishes[num2].x = nx;
        fishes[num2].y = ny;
        fishes[num2].d = direct;
        board[nx][ny] = num2;
        board[x][y] = num1;
    }

    public static void copy(int[][] board, Fish[] fishes, int[][] _board, Fish[] _fishes) {
        for(int i=0; i<4; i++) {
            for(int j=0; j<4; j++) {
                board[i][j] = _board[i][j];
            }
        }
        for(int i=1; i<=16; i++) {
            Fish fish = _fishes[i];
            fishes[i] = new Fish(fish.x, fish.y, fish.d, fish.alive);
        }
    }
}