[BOJ - JAVA] 19236 - 청소년 상어(시뮬레이션, DFS, 삼성 코테 기출)

# 주소

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

19236번: 청소년 상어

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Fish{
    int num;
    int x;
    int y;
    int dir;
    int alive;
    Fish(int num, int x, int y, int dir, int alive){
        this.num = num;
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.alive = alive;
    }
}
class Solution{
    static int[][] arr;
    static Fish[] fish;
    static int d[][] = {{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
    static int answer = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        arr = new int[4][4];
        fish = new Fish[17];
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 4; j++){
                int x = scan.nextInt();
                int y = scan.nextInt() - 1;
                fish[x] = new Fish(x, i, j, y, 1);
                arr[i][j] = x;
            }
        }
        int nx = 0;
        int ny = 0;
        int nd = fish[arr[0][0]].dir;
        int eat = arr[0][0];
        fish[arr[0][0]].alive = 0;
        arr[0][0] = -1;
        dfs(nx,ny,nd,eat);
        System.out.println(answer);
    }
    static void dfs(int x, int y, int nd, int eat){
        answer = Math.max(answer, eat);
        int[][] tempArr = new int[4][4];
        for(int i = 0; i < 4; i++){
            System.arraycopy(arr[i],0,tempArr[i],0,4);
        }
        Fish[] tempFish = new Fish[17];
        for(int i = 1; i <= 16; i++)
            tempFish[i] = new Fish(fish[i].num,fish[i].x,fish[i].y,fish[i].dir,fish[i].alive);
        moveFish();
        for(int i = 1; i < 4; i++){
            int nx = x + d[nd][0] * i;
            int ny = y + d[nd][1] * i;
            if(nx < 0 || ny < 0 || nx >= 4 | ny >= 4)
                continue;
            if(arr[nx][ny] == 0)
                continue;
            int eatFish = arr[nx][ny];
            int nnd = fish[eatFish].dir;
            arr[x][y] = 0;
            arr[nx][ny] = -1;
            fish[eatFish].alive = 0;

            dfs(nx, ny, nnd, eat + eatFish);

            fish[eatFish].alive = 1;
            arr[x][y] = -1;
            arr[nx][ny] = eatFish;
        }
        for(int i = 0; i < 4; i++)
            System.arraycopy(tempArr[i],0,arr[i],0, 4);
        for(int i = 1; i <= 16; i++)
            fish[i] = new Fish(tempFish[i].num, tempFish[i].x, tempFish[i].y, tempFish[i].dir, tempFish[i].alive);
    }
    static void moveFish(){
        for(int i = 1; i < 17; i++){
            if(fish[i].alive == 0)
                continue;
            int cnt = 0;
            int dir = fish[i].dir;
            int nx = 0, ny = 0;
            while(cnt < 8){
                dir %= 8;
                fish[i].dir = dir;
                nx = fish[i].x + d[dir][0];
                ny = fish[i].y + d[dir][1];
                if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4){
                    dir++;
                    cnt++;
                    continue;
                }
                if(arr[nx][ny] == -1) {
                    cnt++;
                    dir++;
                    continue;
                }
                if(arr[nx][ny] == 0){
                    arr[fish[i].x][fish[i].y] = 0;
                }else{
                    int changeFish = fish[arr[nx][ny]].num;
                    fish[changeFish].x = fish[i].x;
                    fish[changeFish].y = fish[i].y;
                    arr[fish[changeFish].x][fish[changeFish].y] = changeFish;
                }
                fish[i].x = nx;
                fish[i].y = ny;
                arr[nx][ny] = i;
                break;
            }
        }
    }
}

이전에 풀었던 아기 상어의 문제보다 조금 더 어려운 유형의 시뮬레이션 문제입니다.

이 문제를 제대로 이해하기 위해서는 지금까지 배웠던 자료구조를 활용할줄 알아야 할 뿐만 아니라 클래스의 객체를 새로 생성하여 저장하고 사용하는 것에 익숙하여야 하며 재귀 함수를 활용한 백트래킹 방식으로 풀어야 하기 때문에 함수를 다시 되돌리는 것에도 익숙하여야 겠습니다.

따라서 클래스 오버로딩도 필수불가결하게 사용됩니다.

차근차근 살펴보겠습니다.

import java.util.*;
class Fish{
    int num;
    int x;
    int y;
    int dir;
    int alive;
    Fish(int num, int x, int y, int dir, int alive){
        this.num = num;
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.alive = alive;
    }
}

Fish라는 클래스를 오버로딩하는데 num, x, y, dir, alive라는 총 5가지의 변수를 사용할 것입니다.

num은 먹이가 될 물고기의 번호를, x와 y는 인덱스, dir는 방향, alive는 살아있는 유무를 판단합니다.

 

그리고 전역 변수로는 arr와 fish, 8방향 벡터, 정답이 될 answer라고 합시다.

 static int[][] arr;
    static Fish[] fish;
    static int d[][] = {{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
    static int answer = 0;

이후 입력값의 양이 적기 때문에 Scanner를 사용하여 입력 받습니다.

Scanner scan = new Scanner(System.in);
        arr = new int[4][4];
        fish = new Fish[17];
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 4; j++){
                int x = scan.nextInt();
                int y = scan.nextInt() - 1;
                fish[x] = new Fish(x, i, j, y, 1);
                arr[i][j] = x;
            }
        }

arr는 4 x 4이고 fish는 16번까지 들어갈 수 있으므로 17의 크기로 선언ㄴ합니다.

또한 2중 for문을 이용하여 x와 y를 입력 받는데, x는 물고기의 값을 의미하고 y는 방향을 의미합니다.

이 때 방향은 0 ~ 7 인덱스에 대해 사용할 것이므로 입력값에서 1뺀 값을 y로 저장합니다.

이후 각 fish물고기에는 새로운 Fish 객체가 생성되어 (물고기 번호, 인덱스 x, 인덱스 y, 방향, 생존)이렇게 삽입됩니다.

그리고 arr에는 x를 삽입해줍시다.

    int nx = 0;
        int ny = 0;
        int nd = fish[arr[0][0]].dir;
        int eat = arr[0][0];
        fish[arr[0][0]].alive = 0;
        arr[0][0] = -1;
        dfs(nx,ny,nd,eat);

이후 상어의 위치를 arr에 심어야 하기 때문에 nx와 ny를 0으로 저장하고

nd에는 arr[0][0]에 있던 방향을 담습니다.

그리고 eat에 arr[0][0]을 넣고 alive 유무는 0으로 바꾼 후 arr값에 현재의 상어 값인 -1을 삽입합니다.

dfs에 이 모든 nx, ny, nd, eat을 넣고 물고기와 상어를 이동시켜봅시다.

static void dfs(int x, int y, int nd, int eat){
        answer = Math.max(answer, eat);
        int[][] tempArr = new int[4][4];
        for(int i = 0; i < 4; i++){
            System.arraycopy(arr[i],0,tempArr[i],0,4);
        }
        Fish[] tempFish = new Fish[17];
        for(int i = 1; i <= 16; i++)
            tempFish[i] = new Fish(fish[i].num,fish[i].x,fish[i].y,fish[i].dir,fish[i].alive);

지금부터 블로그에서 다룬 적은 없었던 내용을 말씀드릴 것입니다.

'얕은 복사'와 '깊은 복사'에 대해서 말입니다.

제가 지금껏 배열을 복사할 때 어떻게 했는지 기억나시나요?

1차원 배열에 대해서는 clone()함수를 썼으나 2차원 배열에 대해서는 for문을 이용하여 저장했습니다.

2차원은 왜 clone()함수가 안먹힐까 싶어서 확인해봤는데 자바에서 2차원부터는 새로 객체를 생성해야 한다고 합니다.

또는 System.arraycopy함수를 사용하여 깊은 복사를 할 수 있다고 합니다.

만약 얕은복사로 배열을 복사할 경우 배열 값이 수정되면 입력했던 값들이 영향을 받아 변경될 수 있습니다.

자세한건 https://woovictory.github.io/2020/04/22/Java-Array-Copy/

[Java] 얕은 복사와 깊은 복사

여기서 확인할 수 있습니다.

다시 본론으로 들어갑니다.

저는 arr의 복사본, fish의 복사본을 가지고 백트래킹 방식을 이용하여 각 배열들의 값들을 분기시키고 싶습니다.

이를 위해선 재귀함수가 당연히 필요할 것이고 손상받지 않을 배열도 같이 필요하겠지요.

우리가 arr를 바꾸는 것은 일시적으로 바꾸는 것만 허락되며 기존의 arr의 변경 전의 배열은 tempArr에 담고 tempFish에 담아서 arr와 fish들이 다시 돌아오는 겁니다.

이렇게 생각해봅시다.

우리들은 게임을 하고 있습니다.

그 게임은 미로 탈출 게임이에요. 

주인공 입장에선 자기가 죽을지 모르지만 우리 플레이어들은 죽으면 게임을 분기점으로 돌아가서 다시 할 수있죠.

딱 여기다 싶었다고 들어갔는데 지뢰나 벽을 마주쳤어요. 그래서 더 이상 이동할 수 없게 되었죠.

그래서 그 주인공캐릭터는 죽어요.

하지만 괜찮아요. 우리에겐 세이브 파일이 있으니까요.

여기서 세이브 파일 역할을 하는 것이 tempArr와 tempFish입니다.

이동했는데 원하는 곳이 아니라면 다시 돌아가서 새로운 시작을 할 수 있습니다.

이를 위해 깊은 복사가 반드시 필요한 것입니다.

moveFish()를 살펴봅시다. (물고기 이동)

static void moveFish(){
        for(int i = 1; i < 17; i++){
            if(fish[i].alive == 0)
                continue;
            int cnt = 0;
            int dir = fish[i].dir;
            int nx = 0, ny = 0;
            while(cnt < 8){
                dir %= 8;
                fish[i].dir = dir;
                nx = fish[i].x + d[dir][0];
                ny = fish[i].y + d[dir][1];
                if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4){
                    dir++;
                    cnt++;
                    continue;
                }
                if(arr[nx][ny] == -1) {
                    cnt++;
                    dir++;
                    continue;
                }
                if(arr[nx][ny] == 0){
                    arr[fish[i].x][fish[i].y] = 0;
                }else{
                    int changeFish = fish[arr[nx][ny]].num;
                    fish[changeFish].x = fish[i].x;
                    fish[changeFish].y = fish[i].y;
                    arr[fish[changeFish].x][fish[changeFish].y] = changeFish;
                }
                fish[i].x = nx;
                fish[i].y = ny;
                arr[nx][ny] = i;
                break;
            }
        }

다음과 같습니다.

 for(int i = 1; i < 17; i++){
            if(fish[i].alive == 0)
                continue;

우리는 물고기를 1번부터 17번까지 탐색할 것인데 해당 세이브파일까지의 물고기가 없다면 continue할 것입니다.

따라서 살아 있는 물고기(먹히지 않은)에 대해서만 탐색할 거에요.

int cnt = 0;
            int dir = fish[i].dir;
            int nx = 0, ny = 0;

cnt는 0으로, dir은 현재 물고기의 방향을, nx와 ny에는 0을 삽입합니다.

cnt는 탐색 횟수를 의미합니다.

while(cnt < 8){
                dir %= 8;
                fish[i].dir = dir;
                nx = fish[i].x + d[dir][0];
                ny = fish[i].y + d[dir][1];
                if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4){
                    dir++;
                    cnt++;
                    continue;
                }
                if(arr[nx][ny] == -1) {
                    cnt++;
                    dir++;
                    continue;
                }

while문으로 탐색하겠습니다.

dir는 8로 나눈 나머지가 될 것입니다.

fish[i] (i번 물고기)의 방향은 만약 이동 가능한 물고기라면 dir을 삽입합니다.

만약 장애물 없이 그대로 이동 가능하다면 현재 있는 방향대로 이동할 것입니다.

그리고 nx와 ny에는 i번의 물고기의 인덱스에 방향만큼 더한 값을 새로 지정합니다.

그리고 이 때 nx, ny와 인덱스 범위를 벗어나면 dir를 증가, cnt도 증가시켜주는데 dir은 증가할 때마다 45도씩 회전합니다.

또한 cnt도 증가시켜 8이 되면 자동으로 break될 것입니다.

arr가 -1일 때에도 마찬가지입니다.

상어가 있는 위치라면 회전시켜주겠습니다.

}
                if(arr[nx][ny] == 0){
                    arr[fish[i].x][fish[i].y] = 0;
                }else{
                    int changeFish = fish[arr[nx][ny]].num;
                    fish[changeFish].x = fish[i].x;
                    fish[changeFish].y = fish[i].y;
                    arr[fish[changeFish].x][fish[changeFish].y] = changeFish;
                }
                fish[i].x = nx;
                fish[i].y = ny;
                arr[nx][ny] = i;
                break;
            }

이후 arr가 0인 곳이라면 arr의 현재 물고기가 있던 점을 0으로 바꿀 것이며(빈칸)

만약 물고기가 있는 지점이라면 서로 스위칭을 하겠습니다.

현재의 물고기 위치와 새로 갱신된 물고기를 서로 바꾸는 것입니다.

여기서 의구심이 생기셔야 정상입니다.

그럼 방향은.. 안 바꾸어주어도 되나요???

네 안바꾸어도 됩니다.

예를 들어 봅시다.

(1,2)의 방향 2

(2,3)의 방향 4인 arr를 서로 바꿔봅시다.

그렇담 (1,2)의 방향 4, (2,3)의 방향 2인 arr가 되어야 합니다.

그렇담 dir들은 서로 가만히 있되 x와 y들끼리만 바꾸면 되는 것입니다.

num도 물론 포함해서말이지요.

이 작업이 끝나면 break해주어 while문을 빠져나오게 하여 moveFish()의 함수를 종료합니다.

for(int i = 1; i < 4; i++){
            int nx = x + d[nd][0] * i;
            int ny = y + d[nd][1] * i;
            if(nx < 0 || ny < 0 || nx >= 4 | ny >= 4)
                continue;
            if(arr[nx][ny] == 0)
                continue;
            int eatFish = arr[nx][ny];
            int nnd = fish[eatFish].dir;
            arr[x][y] = 0;
            arr[nx][ny] = -1;
            fish[eatFish].alive = 0;

            dfs(nx, ny, nnd, eat + eatFish);

            fish[eatFish].alive = 1;
            arr[x][y] = -1;
            arr[nx][ny] = eatFish;
        }

이후 상어의 이동에 대해 살펴봅시다.

arr의 배열은 무조건 4 x 4이기 때문에 대각선으로 이동한다 하더라도 최대 3칸의 범위까지 이동이 가능합니다.

따라서 새로 이동될 nx와 ny 값은 현재의 x,y의 값에 방향 벡터만큼 곱한 값 x i(i는 1과 4 사이)만큼 이동할 수 있습니다.

물론 이 새로 지정한 인덱스들이 0보다 작거나 4보다 크거나 같아지면 continue해야 하며 0인 지점(먹이가 없는 지점)에 대해서도 continue해줍니다.

 int eatFish = arr[nx][ny];
            int nnd = fish[eatFish].dir;
            arr[x][y] = 0;
            arr[nx][ny] = -1;
            fish[eatFish].alive = 0;

            dfs(nx, ny, nnd, eat + eatFish);

            fish[eatFish].alive = 1;
            arr[x][y] = -1;
            arr[nx][ny] = eatFish;
        }

그리고 먹이가 있는 값에 대해서는 eatFish에 먹이를 담고 nnd에는 먹이의 방향을 담겠습니다.

만약 상어가 먹이를 먹어 치우면 해당 위치의 방향을 가져오기 때문에 그렇습니다.

상어가 먹이를 드디어 먹습니다.

이 때에는 arr의 현재 x와 y의 위치에 대해서는 0으로 저장하며 먹이는 사라집니다.

그리고 새로 지정한 nx와 ny의 위치에 상어가 존재하므로 -1을 저장하고 fish의 생존은 0으로 바꿉니다.

그리고 dfs를 이어서 진행합니다.

이 때 담긴 arr에는 방금 먹이가 먹힌 뒤의 arr를 가지고 계속해서 분기하는 것입니다.

또한 dfs가 마쳐진 뒤에 바로 마지막 세이브 파일의 전 단계로 돌아가서 새로 분기를 하여야 합니다.

그러니까 이 표를 보시면

1 - 2 - 3

   - 4 - 5

         - 6

이렇게 분기된다 할 때(방법을 모르겠어서...)

맨 오른쪽의 3이 실패하면 2로 돌아가고 그 전인 1로 돌아가서 4로 시행하여 5를 시행하고 다시 돌아가서 6도 실행한다는 것이 이 백트래킹의 기본 원리입니다.

그러므로 먹이를 되돌려 놓으려면 dfs뒤에 한 번더 코드를 입력해주어야 겠습니다.

 fish[eatFish].alive = 1;
            arr[x][y] = -1;
            arr[nx][ny] = eatFish;
        }

다음과 같습니다.

fish의 물고기를 1로 바꾸어 주고 원래 있던 arr의 x와 y에 -1을 삽입하며 아까 새로 이동했던 nx와 ny의 인덱스에 대해서 먹이를 넣어줍니다.

그럼 원래대로의 arr로 돌아오게 되는 것입니다.

하지만 여기서 끝나지 않습니다.

}
        for(int i = 0; i < 4; i++)
            System.arraycopy(tempArr[i],0,arr[i],0, 4);
        for(int i = 1; i <= 16; i++)
            fish[i] = new Fish(tempFish[i].num, tempFish[i].x, tempFish[i].y, tempFish[i].dir, tempFish[i].alive);
    }

기존의 arr와 fish를 tempArr와 tempFish에 저장해 두었던 것 기억하실 겁니다.

다시 arr와 fish도 세이브해두었던 temp들을 이용하여 깊은 복사로 돌려주어야 겠습니다.

 

백트래킹은 이래서 참 편리합니다.

저희가 따로 범위를 지정해두지 않고 원상복구만 잘 입력해주어도 자기 알아서 완전 탐색을 처리해줍니다.

물론 복귀하는 것이 어렵지만 저도 이 문제를 통해 공부를 많이 했던 것 같습니다.

예상되로 answer를 출력하면 정답이 되겠습니다.

감사합니다.