[백준 19236 / JAVA] 청소년 상어

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

19236번: 청소년 상어

 

요즘 구현과 백트레킹 문제를 많이 푸는 것 같다.

 

처음에는 4X4 이차원 배열에 물고기를 저장해 풀려고 했다.

하지만 풀다보니 물고기 클래스 자체에 좌표를 저장하고 이차원 배열을 쓰지 않는 것이 구현하기 더 편한 것 같아 방식을 바꾸었다.

 

이 문제를 풀면서 문제를 어떻게 푸는지 알아내는 것 보다 깊은 복사를 자바로 쉽게 하는 방법이 있어 따라했지만 되지 않아 원래 깊은 복사를 하던 방식으로 했다. addAll을 하면 자동으로 깊은 복사가 된다고 하는데 다시 알아봐야겠다.

 

이 문제는 문제 그대로 구현을 하면 된다.

상어가 이동하는 부분 다음으로 물고기들이 이동하는 부분을 차례로 구현하고 상어가 이동하는 부분을 DFS로 모든 경우를 보도록 했다.

 

c++에서 자바로 옮긴지 얼마 안되어서 그런지 자바의 방식을 알아보는게 더 오래 걸린다...

 

    static List<Fish> fishList = new ArrayList<Fish>();
    static int result = 0;

    public static class Fish implements Comparable<Fish> {
        int x, y, num, dir;
        boolean alive;

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

        @Override
        public int compareTo(Fish fish) {
            return this.num - fish.num;
        }
    }

Fish 클래스에는 물고기의 x, y 좌표, 번호, 방향, 생존 여부를 나타내는 변수를 만들었다.

compareTo는 물고기를 num 기준으로 나중에 정렬하기 위해 Comparable을 상속받아 Override 했다.

fishList는 Fish 클래스를 리스트 형태로 가진다.

 

    public static class Shark {
        int x, y, dir;

        public Shark(int x, int y, int dir) { //상어
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }

상어 클래스이다. 좌표, 방향을 가진다.

 

    public static void DFS(Shark shark, List<Fish> fishList) {
        int dx, dy; //바꿀 물고기 좌표
        int[] dfx = {0, -1, -1, 0, 1, 1, 1, 0, -1};
        int[] dfy = {0, 0, -1, -1, -1, 0, 1, 1, 1};

        //물고기 이동
        for (int i = 0; i < fishList.size(); i++) {
            if (fishList.get(i).alive == true) {
                int cnt = 0;// 이동 가능한지 확인
                while (true) {
                    dx = fishList.get(i).x;
                    dy = fishList.get(i).y;
                    dx += dfx[fishList.get(i).dir];
                    dy += dfy[fishList.get(i).dir];

                    //이동 가능
                    if (dx >= 0 && dy >= 0 && dx < 4 && dy < 4 && (dx != shark.x || dy != shark.y)) {
                        int index = getfishindex(dx, dy, fishList);
                        int tempx, tempy;
                        tempx = fishList.get(i).x;
                        tempy = fishList.get(i).y;
                        fishList.get(i).x = fishList.get(index).x;
                        fishList.get(i).y = fishList.get(index).y;
                        fishList.get(index).x = tempx;
                        fishList.get(index).y = tempy;
                        break;
                    } else cnt++;

                    fishList.get(i).dir++;
                    if (fishList.get(i).dir > 8) fishList.get(i).dir = 1;
                    if (cnt > 7) break;
                }
            }
        }

DFS 함수 중 물고기를 이동시키는 부분이다.

dfx와 dfy는 이동할 물고기 좌표의 변화값이다. 0은 0으로 채우고 1부터 8 까지가 각 방향이다.

dx와 dy는 물고기가 이동할 좌표이다.

 

만약 이동이 가능하다면

이동할 위치의 물고기의 index를 찾아 서로의 좌표를 바꿔준다.

cnt는 물고기의 방향이 한바퀴만 돌도록 확인하는 용도이다.

 

        int sx, sy;
        int[] sdx = {0, -1, -1, 0, 1, 1, 1, 0, -1};
        int[] sdy = {0, 0, -1, -1, -1, 0, 1, 1, 1};
        sx = shark.x;
        sy = shark.y;
        //상어 이동
        while (true) { //상어가 이동 가능할 동안 반복
            sx += sdx[shark.dir];
            sy += sdy[shark.dir];

            if (sx >= 0 && sy >= 0 && sx < 4 && sy < 4) {//이동가능
                shark.x = sx;
                shark.y = sy;
                if (fishList.get(getfishindex(sx, sy, fishList)).alive == Boolean.TRUE) {
                    List<Fish> tempfishList;
                    tempfishList = copyArray(fishList); //새로운 물고기 리스트 생성
                    tempfishList.get(getfishindex(sx, sy, fishList)).alive = Boolean.FALSE;
                    Shark tempshark = new Shark(shark.x, shark.y, shark.dir);
                    tempshark.dir = tempfishList.get(getfishindex(sx, sy, tempfishList)).dir;
                    DFS(tempshark, tempfishList);
                }
            } else break;
        }
        int sum = 0;
        for (int i = 0; i < fishList.size(); i++) {
            if (fishList.get(i).alive == Boolean.FALSE)
                sum += fishList.get(i).num;
        }
        if (result < sum) result = sum;
    }

상어가 이동하는 부분이다.

sdx와 sdy는 이동할 상어 좌표의 변화값이다. 0은 0으로 채우고 1부터 8 까지가 각 방향이다.

sx와 sy가 상어가 이동할 좌표이다.

 

상어가 이동 가능하다면 이동할 위치의 물고기가 살아있을 경우에만 이동한다.

tempfishList는 재귀호출할 DFS에 들어갈 새로운 물고기 리스트이다.

copyArray 함수를 통해 깊은 복사를 한다. 해당하는 물고기의 alive를 false로 만들어준다.

 

상어 객체로 깊은 복사를 통해 생성한다.

상어의 방향을 바꾸고 DFS를 재귀호출한다.

 

sum변수에 죽어있는 물고기의 번호를 합한다.

그 중 최댓값을 구한다.

 

    public static List<Fish> copyArray(List<Fish> fishList) {
        List<Fish> tempfishList = new ArrayList<Fish>();
        fishList.forEach(t -> tempfishList.add(new Fish(t.x, t.y, t.num, t.dir, t.alive)));
        return tempfishList;
    }

깊은 복사를 해준다.

 

반응형

 

전체코드

import java.util.*;

public class Main {
    static List<Fish> fishList = new ArrayList<Fish>();
    static int result = 0;

    public static class Fish implements Comparable<Fish> {
        int x, y, num, dir;
        boolean alive;

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

        @Override
        public int compareTo(Fish fish) {
            return this.num - fish.num;
        }
    }

    public static class Shark {
        int x, y, dir;

        public Shark(int x, int y, int dir) { //상어
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }

    public static void DFS(Shark shark, List<Fish> fishList) {
        int dx, dy; //바꿀 물고기 좌표
        int[] dfx = {0, -1, -1, 0, 1, 1, 1, 0, -1};
        int[] dfy = {0, 0, -1, -1, -1, 0, 1, 1, 1};

        //물고기 이동
        for (int i = 0; i < fishList.size(); i++) {
            if (fishList.get(i).alive == true) {
                int cnt = 0;// 이동 가능한지 확인
                while (true) {
                    dx = fishList.get(i).x;
                    dy = fishList.get(i).y;
                    dx += dfx[fishList.get(i).dir];
                    dy += dfy[fishList.get(i).dir];

                    //이동 가능
                    if (dx >= 0 && dy >= 0 && dx < 4 && dy < 4 && (dx != shark.x || dy != shark.y)) {
                        int index = getfishindex(dx, dy, fishList);
                        int tempx, tempy;
                        tempx = fishList.get(i).x;
                        tempy = fishList.get(i).y;
                        fishList.get(i).x = fishList.get(index).x;
                        fishList.get(i).y = fishList.get(index).y;
                        fishList.get(index).x = tempx;
                        fishList.get(index).y = tempy;
                        break;
                    } else cnt++;

                    fishList.get(i).dir++;
                    if (fishList.get(i).dir > 8) fishList.get(i).dir = 1;
                    if (cnt > 7) break;
                }
            }
        }

        int sx, sy;
        int[] sdx = {0, -1, -1, 0, 1, 1, 1, 0, -1};
        int[] sdy = {0, 0, -1, -1, -1, 0, 1, 1, 1};
        sx = shark.x;
        sy = shark.y;
        //상어 이동
        while (true) { //상어가 이동 가능할 동안 반복
            sx += sdx[shark.dir];
            sy += sdy[shark.dir];

            if (sx >= 0 && sy >= 0 && sx < 4 && sy < 4) {//이동가능
                shark.x = sx;
                shark.y = sy;
                if (fishList.get(getfishindex(sx, sy, fishList)).alive == Boolean.TRUE) {
                    List<Fish> tempfishList;
                    tempfishList = copyArray(fishList); //새로운 물고기 리스트 생성
                    tempfishList.get(getfishindex(sx, sy, fishList)).alive = Boolean.FALSE;
                    Shark tempshark = new Shark(shark.x, shark.y, shark.dir);
                    tempshark.dir = tempfishList.get(getfishindex(sx, sy, tempfishList)).dir;
                    DFS(tempshark, tempfishList);
                }
            } else break;
        }
        int sum = 0;
        for (int i = 0; i < fishList.size(); i++) {
            if (fishList.get(i).alive == Boolean.FALSE)
                sum += fishList.get(i).num;
        }
        if (result < sum) result = sum;
    }

    public static int getfishindex(int x, int y, List<Fish> fishList) {
        for (int i = 0; i < fishList.size(); i++) {
            if (fishList.get(i).x == x && fishList.get(i).y == y)
                return i;
        }
        return -1;
    }

    public static void printFish(List<Fish> fishList) {
        for (int i = 0; i < fishList.size(); i++) {
            System.out.println(" x : " + fishList.get(i).x + " y : " + fishList.get(i).y + " num : " + fishList.get(i).num + " alive : " + fishList.get(i).alive);
        }
    }

    public static List<Fish> copyArray(List<Fish> fishList) {
        List<Fish> tempfishList = new ArrayList<Fish>();
        fishList.forEach(t -> tempfishList.add(new Fish(t.x, t.y, t.num, t.dir, t.alive)));
        return tempfishList;
    }

    public static void main(String[] args) {
        int num, dir;
        Shark shark = null;
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                num = sc.nextInt();
                dir = sc.nextInt();
                if (i == 0 && j == 0) {
                    shark = new Shark(0, 0, dir);
                    fishList.add(new Fish(i, j, num, dir, Boolean.FALSE));
                } else fishList.add(new Fish(i, j, num, dir, Boolean.TRUE));
            }
        }
        fishList.sort(Comparator.naturalOrder());

        DFS(shark, fishList);

        System.out.println(result);
    }
}