백준 19236 (청소년 상어)

문제

19236번: 청소년 상어

4 * 4 크기의 칸에서 1 ~ 16번까지의 물고기가 들어간다.

처음 상어는 [0][0]에서 물고기를 먹고 물고기는 이동한다. 

물고기가 이동하면 상어는 방향에 따라 갈 수 있는 공간에서 물고기를 하나 먹을 수 있다. 이러한 반복을 상어가 물고기를 못먹을 때 까지

반복한다.

정리하면 다음과 같다.

1. 상어는 물고기를 먹을 수 있으면 먹는다.

2. 1번 물고기 부터 시작해서 16번 물고기 까지 이동을 한다. 만약 이동을 못하게 되면 45도 반시계 방향으로 방향을 바꾸면서 이동할 수 있      는지 없는지 확인한다.

    이동을 못하는 경우는 맵을 벗어나거나, 이동할 위치에 상어가 있는 것이다.

 

3. 상어는 현재 방향에서 맵을 벗어나기 전까지 물고기를 1마리 먹을 수 있다.

 

1 -> 2 -> 3이 계속 반복된다.

상어가 먹은 물고기번호의 합의 최댓값을 구하라.

 

먼저 처음 맵이 위와 같다고 하자.

상어가 처음에 [0][0]을 먹는다.

1번 물고기부터 이동했다. 15번과 1번이 자리가 바뀐것을 알 수 있다.

위에 그림은 1 ~ 16의 물고기가 모두 이동을 한 그림이다.

이제 상어는 상어 방향에 따라 맵 벗어나기 전까지 12, 15, 8중 한 마리의 물고리를 먹을 수 있다.

---

물고기의 번호가 최대가 되어야 한다. 어떻게 해야할까?

바로 다 둘러보는 것이다. 어떻게? dfs방법으로 ...

보시다 시피 상어는 방향이 맞고 map을 벗어나지 않으면 최대 3마리중 한마리를 먹을 수 있다.

즉, dfs을 돌아보면서 최댓값을 갱신해주는것이 해당 문제의 큰 틀이다.

 

먼저 입력 부분부터 보자.

class Fish{
    int x;
    int y;
    int num; //물고기 번호
    int dir; //물고기 방향
    boolean isAlive; //현재 물고기 죽었는지 살았는지

    public Fish(int x, int y, int num, int dir, boolean isAlive) {
        this.x = x;
        this.y = y;
        this.num = num;
        this.dir = dir;
        this.isAlive =isAlive;
    }
}
class Shark{
    int x;
    int y;
    int dir;
    int eatSum; //먹은 물고기 번호의 누적합

    public Shark(int x, int y, int dir, int eatSum) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.eatSum = eatSum;
    }
}


int[][]arr = new int[4][4];
        List<Fish> fishes = new ArrayList<>();

        for(int i=0;i<4;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<4;j++){
                int num = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken()) -1; //주의

                Fish f = new Fish(i, j, num, dir, true);
                arr[i][j] = num;
                fishes.add(f);
            }
        }

새로운 클래스인 Fish와 Shark를 만들었다.

또한 방향을 입력받을 때는 1 ~ 8로 주어진다. ↑, ↖, ←, ↙, ↓, ↘, →, ↗  따라서 우리는 dx[], dy[]로 작업해야 하기 때문에 배열 인덱스

때문에 -1을 해주어 입력을 받아주었다.

 

arr은 4 * 4배열이고 각 칸마다 물고기의 번호가 들어가 있다.

fishes는 현재 살아있든, 죽어있든 모든 물고기를 넣어준다. 1 ~ 16

Collections.sort(fishes, new Comparator<Fish>(){
            @Override
            public int compare(Fish o1, Fish o2){
                return o1.num - o2.num;
            }
        });

그 다음 입력받은 fishes의 리스트를 물고기의 번호를 기준으로 오름차순으로 정렬한다.

1번 물고기 부터 이동을 하기 때문이다.

따라서 나중에 특정 번호의 물고기를 조회하고 싶으면 fishes.get(arr[i][j] -1) 로 조회하면 된다.

arr[i][j]에는 (i, j) 에 있는 물고기의 번호가 있기 때문에 해당 번호 -1을 해주어야 리스트에 접근할 수 있다.

 

Fish f = fishes.get(arr[0][0] - 1); //[0][0]에 있는 먹이 물고기
        Shark shark = new Shark(0, 0, f.dir, f.num);
        f.isAlive = false;
        arr[0][0] = -1;

상어가 [0][0]에 있는 물고기를 먹는 코드이다.

물고기를 먹고 이제는 1번 물고기 부터 16번 물고기 까지 이동을 하면된다.

private static void eat(int[][] arr,Shark shark, List<Fish>fishes){

        ans = Math.max(ans, shark.eatSum);

        for(Fish f : fishes){

            if(!f.isAlive)continue;

            for(int i=0;i<8;i++){
                int nxtDir = (f.dir + i) % 8;
                int xx = f.x + dx[nxtDir];
                int yy = f.y + dy[nxtDir];

                if(xx<0||yy<0||xx>=4||yy>=4 || arr[xx][yy] <= -1)continue;
                arr[f.x][f.y] = 0;

                if(arr[xx][yy] == 0){
                    f.x = xx;
                    f.y = yy;
                }
                else{
                    Fish target = fishes.get(arr[xx][yy]-1);
                    target.x = f.x;
                    target.y = f.y;
                    arr[f.x][f.y] = target.num;

                    f.x = xx;
                    f.y = yy;
                }

                arr[xx][yy] = f.num;
                f.dir = nxtDir;
                break;
            }
        }


        for(int i=1;i<4;i++){
            int xx = shark.x + dx[shark.dir] * i;
            int yy = shark.y + dy[shark.dir] * i;

            if(xx<0||yy<0||xx>=4||yy>=4||arr[xx][yy] <= 0)continue;
            int[][]arrCopies = copyArr(arr);
            List<Fish>fishCopies = copyFishes(fishes);

            arrCopies[shark.x][shark.y] = 0;
            Fish feet = fishCopies.get(arr[xx][yy] - 1);
            Shark newShark = new Shark(feet.x, feet.y, feet.dir, shark.eatSum + feet.num);
            feet.isAlive = false;
            arrCopies[feet.x][feet.y] = -1;

            eat(arrCopies, newShark, fishCopies);
        }


    }

이제 본격적인 dfs과정이다.

dfs의 인자로, arr, shark, fishes를 넘겨주었다.

만약 해당 데이터를 전역변수로 설정하면 dfs하는 동안 동시에 바뀌므로 인자로 넣어 주었다.

for(Fish f : fishes){

            if(!f.isAlive)continue; //현재 물고기가 죽었으면 continue	
			
            //먼저 현재 방향부터 순회
            for(int i=0;i<8;i++){
                int nxtDir = (f.dir + i) % 8;
                int xx = f.x + dx[nxtDir];
                int yy = f.y + dy[nxtDir];
				
                //맵을 벗어나거나 상어 일 경우 (이동 불가)
                if(xx<0||yy<0||xx>=4||yy>=4 || arr[xx][yy] <= -1)continue; 
                arr[f.x][f.y] = 0;

                if(arr[xx][yy] == 0){ //갈려는 위치에 아무것도 없을 경우 
                    f.x = xx;
                    f.y = yy;
                }
                else{ //갈려는 위치에 다른 물고기가 있을 경우
                    Fish target = fishes.get(arr[xx][yy]-1); //해당 위치에 있는 물고기
                    target.x = f.x;
                    target.y = f.y;
                    arr[f.x][f.y] = target.num;

                    f.x = xx;
                    f.y = yy;
                }

                arr[xx][yy] = f.num;
                f.dir = nxtDir;
                break;
            }
        }

위의 코드는 1번 물고기 부터 현재 방향으로 이동하는 코드이다.

for(int i=1;i<4;i++){ //상어는 최대 3칸 이동이 가능하다.
            int xx = shark.x + dx[shark.dir] * i;
            int yy = shark.y + dy[shark.dir] * i;

            if(xx<0||yy<0||xx>=4||yy>=4||arr[xx][yy] <= 0)continue; //맵을 벗어나거나 먹을 물고기가 없을 경우
            int[][]arrCopies = copyArr(arr); //현재 arr배열 복사
            List<Fish>fishCopies = copyFishes(fishes); //현재 fishes 리스트 복사

            arrCopies[shark.x][shark.y] = 0; //현재 상어 위치는 상어가 다음 물고기를 먹으러 이동할 것이기 때문에 0으로 초기화
            Fish feet = fishCopies.get(arr[xx][yy] - 1); //현재 먹힐 물고기
            Shark newShark = new Shark(feet.x, feet.y, feet.dir, shark.eatSum + feet.num); //상어의 위치 이동
            feet.isAlive = false; //물고기는 먹힘
            arrCopies[feet.x][feet.y] = -1; //먹힌 물고기 위치에 -1 표시 (상어 위치 이기 때문)

            eat(arrCopies, newShark, fishCopies); //dfs 
        }

위의 코드는 상어가 먹이를 먹는 코드이다. 

상어는 같은 방향으로 최대 3번 이동하기 때문에 3번 반복해준다.

여기서 중요한것이 dfs를 하는동안 arr과 fishes의 리스트 값들이 변경된다.

다음 dfs를 할 때는 변경된 값들을 사용하면 안되기 때문에 arr배열과 fishes리스트를 복사해주었다.

private static int[][] copyArr(int[][]arr){
        int[][]temp = new int[4][4];

        for(int i=0;i<4;i++){
            for(int j = 0;j<4;j++){
                temp[i][j] = arr[i][j];
            }
        }
        return temp;
    }
    
private static List<Fish> copyFishes(List<Fish>fishes){
        List<Fish>temp = new ArrayList<>();
        fishes.forEach(e -> temp.add(new Fish(e.x, e.y, e.num, e.dir, e.isAlive)));        return temp;
    }

---

전체 코드이다.

public class Main {
    private static int []dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    private static int []dy = {0, -1, -1, -1, 0, 1, 1, 1};
    private static int ans=0;

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

        int[][]arr = new int[4][4];
        List<Fish> fishes = new ArrayList<>();

        for(int i=0;i<4;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<4;j++){
                int num = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken()) -1;

                Fish f = new Fish(i, j, num, dir, true);
                arr[i][j] = num;
                fishes.add(f);
            }
        }

        Collections.sort(fishes, new Comparator<Fish>(){
            @Override
            public int compare(Fish o1, Fish o2){
                return o1.num - o2.num;
            }
        });

        Fish f = fishes.get(arr[0][0] - 1); //[0][0]에 있는 먹이 물고기
        Shark shark = new Shark(0, 0, f.dir, f.num);
        f.isAlive = false;
        arr[0][0] = -1;


        eat(arr, shark, fishes);
        System.out.println(ans);
    }
    private static void eat(int[][] arr,Shark shark, List<Fish>fishes){

        ans = Math.max(ans, shark.eatSum);

        for(Fish f : fishes){

            if(!f.isAlive)continue;

            for(int i=0;i<8;i++){
                int nxtDir = (f.dir + i) % 8;
                int xx = f.x + dx[nxtDir];
                int yy = f.y + dy[nxtDir];

                if(xx<0||yy<0||xx>=4||yy>=4 || arr[xx][yy] <= -1)continue;
                arr[f.x][f.y] = 0;

                if(arr[xx][yy] == 0){
                    f.x = xx;
                    f.y = yy;
                }
                else{
                    Fish target = fishes.get(arr[xx][yy]-1);
                    target.x = f.x;
                    target.y = f.y;
                    arr[f.x][f.y] = target.num;

                    f.x = xx;
                    f.y = yy;
                }

                arr[xx][yy] = f.num;
                f.dir = nxtDir;
                break;
            }
        }


        for(int i=1;i<4;i++){
            int xx = shark.x + dx[shark.dir] * i;
            int yy = shark.y + dy[shark.dir] * i;

            if(xx<0||yy<0||xx>=4||yy>=4||arr[xx][yy] <= 0)continue;
            int[][]arrCopies = copyArr(arr);
            List<Fish>fishCopies = copyFishes(fishes);

            arrCopies[shark.x][shark.y] = 0;
            Fish feet = fishCopies.get(arr[xx][yy] - 1);
            Shark newShark = new Shark(feet.x, feet.y, feet.dir, shark.eatSum + feet.num);
            feet.isAlive = false;
            arrCopies[feet.x][feet.y] = -1;

            eat(arrCopies, newShark, fishCopies);
        }


    }
    private static int[][] copyArr(int[][]arr){
        int[][]temp = new int[4][4];

        for(int i=0;i<4;i++){
            for(int j = 0;j<4;j++){
                temp[i][j] = arr[i][j];
            }
        }
        return temp;
    }
    private static List<Fish> copyFishes(List<Fish>fishes){
        List<Fish>temp = new ArrayList<>();
        fishes.forEach(e -> temp.add(new Fish(e.x, e.y, e.num, e.dir, e.isAlive)));        return temp;
    }
}
class Fish{
    int x;
    int y;
    int num;
    int dir;
    boolean isAlive;

    public Fish(int x, int y, int num, int dir, boolean isAlive) {
        this.x = x;
        this.y = y;
        this.num = num;
        this.dir = dir;
        this.isAlive =isAlive;
    }
}
class Shark{
    int x;
    int y;
    int dir;
    int eatSum;

    public Shark(int x, int y, int dir, int eatSum) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.eatSum = eatSum;
    }
}