[백준] 19236 청소년 상어

문제 설명

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

문제 풀이

• 시뮬레이션 문제이다.
• dfs로 구현하였으며 dfs가 진행될 때 이전 상태를 저장하고 restore 해주는 부분에서 삽질을 많이했다... (자바에 좀 더 익숙해져야..)

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static class Fish {
        int x, y, d;
        boolean live;

        public Fish(int x, int y, int d, boolean live) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.live = live;
        }
    }
    public static Fish[] fish = new Fish[17];
    public static int[][] fishMap = new int[4][4];
    public static int result = 0;
    public static int[] dx = {0,-1,-1,0,1,1,1,0,-1};
    public static int[] dy = {0,0,-1,-1,-1,0,1,1,1};

    //상어 위치 (x, y)
    public static void moveFish(int x, int y) {
        for (int i = 1; i <= 16; i++) {
            Fish moveFish = fish[i];
            //죽어있으면 이동X
            if (!moveFish.live) continue;
            //8방향 이동여부 확인
            for (int j = 0; j < 8; j++) {
                int D = (moveFish.d + j) >= 9 ? (moveFish.d + j) % 8 : (moveFish.d + j);
                int X = moveFish.x + dx[D];
                int Y = moveFish.y + dy[D];
                //상어가 있거나 경계를 넘으면 continue
                if (X < 0 || Y < 0 || X >= 4 || Y >= 4 || (X == x && Y == y)) continue;
                //물고기 있으면
                if (fishMap[X][Y] != -1) {
                    Fish otherFish = fish[fishMap[X][Y]];
                    fishMap[moveFish.x][moveFish.y] = fishMap[X][Y];
                    fishMap[X][Y] = i;
                    otherFish.x = moveFish.x;
                    otherFish.y = moveFish.y;
                    moveFish.x = X;
                    moveFish.y = Y;
                    moveFish.d = D;
                //물고기 없으면
                } else {
                    fishMap[moveFish.x][moveFish.y] = -1;
                    fishMap[X][Y] = i;
                    moveFish.x = X;
                    moveFish.y = Y;
                    moveFish.d = D;
                }
                break;
            }

        }
    }

    public static void solve(int x, int y, int d, int sum) {
        //결과값 갱신
        if (result < sum) result = sum;
        //fish, fishMap 상태 저장해둠
        Fish[] fishTmp = new Fish[17];
        for (int i = 1; i < 17; i++)
            fishTmp[i] = new Fish(fish[i].x, fish[i].y, fish[i].d, fish[i].live);
        int[][] fishMapTmp = new int[4][4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                fishMapTmp[i][j] = fishMap[i][j];
            }
        }
        //1. 물고기 이동
        moveFish(x, y);

        //2. 상어 이동
        for (int i = 1; i < 4; i++) {
            int X = x + dx[d]*i;
            int Y = y + dy[d]*i;
            if (X < 0 || Y < 0 || X >= 4 || Y >= 4) break;
            //살아있는 물고기가 있는 경우
            int fishNum = fishMap[X][Y];
            if (fishNum != -1) {
                fish[fishNum].live = false;
                fishMap[X][Y] = -1;
                solve(X, Y, fish[fishNum].d, sum + fishNum);
                fish[fishNum].live = true;
                fishMap[X][Y] = fishNum;
            }
        }

        //fish, fishMap 상태 복구
        for (int i = 1; i < 17; i++) {
            fish[i].x = fishTmp[i].x;
            fish[i].y = fishTmp[i].y;
            fish[i].d = fishTmp[i].d;
            fish[i].live = fishTmp[i].live;
        }
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                fishMap[i][j] = fishMapTmp[i][j];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                int fishNum = sc.nextInt();
                int fishDir = sc.nextInt();
                fishMap[i][j] = fishNum;
                fish[fishNum] = new Fish(i, j, fishDir, true);
            }
        }
        //상어가 첫번째 위치의 물고기 먹음.
        int fishNum = fishMap[0][0];
        fish[fishNum].live = false;
        fishMap[0][0] = -1;
        solve(0, 0, fish[fishNum].d, fishNum);
        System.out.println(result);
    }
}