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

청소년 상어

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	647	396	301	66.593%

문제

아기상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

<그림 1>

<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

<그림 2>

이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

<그림 3>

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

<그림 4>

3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

<그림 5>

물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

<그림 6>

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

예제 입력 1 복사

xxxxxxxxxx
7 6 2 3 15 6 9 8
3 1 1 8 14 7 10 1
6 1 13 6 4 3 11 4
16 1 8 7 5 2 12 2

예제 출력 1 복사

xxxxxxxxxx
33

예제 입력 2 복사

xxxxxxxxxx
16 7 1 4 4 3 12 8
14 7 7 6 3 4 10 2
5 2 15 2 8 3 6 4
11 8 2 4 13 5 9 4

예제 출력 2 복사

xxxxxxxxxx
43

예제 입력 3 복사

xxxxxxxxxx
12 6 14 5 4 5 6 7
15 1 11 7 3 7 7 5
10 3 8 3 16 6 1 1
5 8 2 7 13 6 9 2

예제 출력 3 복사

xxxxxxxxxx
76

예제 입력 4 복사

xxxxxxxxxx
2 6 10 8 6 7 9 4
1 7 16 6 4 2 5 8
3 7 8 6 7 6 14 8
12 7 15 4 11 3 13 3

예제 출력 4 복사

39

 

풀이

삼성 20 상반기 코테 기출문제

 

엄청 고생해서 풀었다... 그 만큼 얻은것도 많을꺼라고 믿는다

map 배열에는 물고기 번호를 넣어주었다.

 

우선 물고기를 표현할 객체를 만들었다.

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

x,y = 좌표

dir = 방향

alive 는 물고기가 상어에게 잡아먹혔는지 여부를 체크하는 것이다.

 

이 문제에서 물고기는 번호가 작은것 부터 움직여야 한다고 하니 맨처음엔 Fish객체에 물고기 번호도 넣어서 내부 정렬을 통해 작은 것 부터 나오도록 해야하나 라고 생각했는데 굳이 그럴 필요 없이

1~16번 물고기의 정보를 갖는 객체를 만들면 됐다

Fish fish[17] 이렇게 정보를 받으면 된다.

그리고 입력을 받을때 물고기번호를 fish[a] = 값값값값 이런식으로 a 에 넣어주면

1~16번 물고기번호를 입력 받을수 있다.

그리고 작은것 부터 움직여야 하는건 그냥 반복문으로

i=1; i<=16; i++ fish[i] <- 이렇게 접근하면 됐다.

 

dfs 진행방향은 이렇다

1. 상어가 물고기를 먹는다
2. 물고기가 이동한다
3. 상어가 다음칸 혹은 다다음칸으로 이동하고 재귀를 통해 1번 부터 다시 시작한다

 

맨 처음에 상어가 0,0 칸을 먹고 시작하니 dfs를 시작 할 때 인자로 주고 시작하면 된다.

(나는 1,1 부터 시작했다)

dfs의 인자에는 총 4개가 들어간다 상어의 x,y좌표 방향 여태까지 먹은 물고기의 수량

 

    fish[map[1][1]].alive = false;
        int tmp_dir = fish[map[1][1]].dir;
        int tmp_fishNum = map[1][1];
        map[1][1] = -1;
        dfs(1,1,tmp_dir,tmp_fishNum);

위의 코드는 입력을 다 받고 시작 하는건데 상어가 첫 칸을 먹고 시작하니

dfs 시작 전에 잡혔다고 표시 해준 셈이다.

tmp_dir = 1,1에 있는 물고기 방향

tmp_fishNum = 1,1에 있는 물고기 번호

 

 

이제 dfs 함수에서 중요한 부분이 있다.

해당칸에 물고기번호를 가지고있는 map 배열과

물고기 정보를 갖고있는 fish 배열을 복사 해두어야 하는 것이다.

맨 처음 백트래킹을 할 때 나는 단지

xxxxxxxxxx
for(int i=0; i<3; i++){
    map[x][y] =0;   // 여기서 0으로 바꿔보고
    dfs(값,값,값,값,값);
    map[x][y] = -1; // 다시 -1 로 되돌리고
}

이런 식으로만 백트래킹을 진행하면 되는 줄 알았다.

이건 백트래킹의 가장 기초적인 로직이라 (삼성 연구소) 이런식으로 진행하면 되는줄 알았는데

이 문제는 좀 많이 복잡했다.

 

우선 상어는 자신의 진행방향에 따라 물고기를 먹을수 있다.

즉 매번 할 때 마다 다른 물고기를 먹을수 있다.

xxxxxxxxxx
for(int i=0; i<3; i++){
    1번 물고기 = 죽음;
    dfs(1번물고기 먹음);
    1번 물고기 = 살음;
}

만약 1번 물고기를 먹었다 치자.

그럼 1번 물고기를 죽이고 dfs함수로 돌아가 1번 물고기가 죽은채로 물고기가 이동한다.

(dfs의 로직은 상어가 물고기를 먹고, 물고기가 움직이고, 상어가 이동하는로직)

그럼 1번 물고기를 먹었다고 가정 했을 경우의 수를 다 훑어 보고

2번 물고기를 먹었다고 가정 했을 경우의 수를 진행 할 때

이미 1번 물고기를 먹었다고 가정하고 진행 할 때 물고기들이 다 이동했기 때문에

2번 물고기를 먹을땐 맨처음 상태의 물고기 상태가아닌 물고기가 1번 물고기가 죽은채로 이미 이동한 상태이다

 

그래서 dfs 안에 copy 배열을 따로 만들었다.

xxxxxxxxxx
public static void dfs(int sx, int sy, int sdir ,int sum) { 
        max = Math.max(max, sum);
        int copy_map[][] = new int[5][5];
        Fish copy_fish[] = new Fish[17];
        for(int i=1; i<=16; i++) {
            copy_fish[i] = new Fish(0,0,0,true);
        }
        copy(copy_map,copy_fish);
}

max = Math.max(max,sum)은 지금 다루지 않는다.

    public static void copy(int copy_map[][], Fish copy_fish[]) {
        for(int i=1; i<=16; i++) {
            copy_fish[i].x = fish[i].x;
            copy_fish[i].y = fish[i].y;
            copy_fish[i].dir = fish[i].dir;
            copy_fish[i].alive = fish[i].alive;
        }
        for(int i=1; i<=4; i++) {
            for(int j=1; j<=4; j++) {
                copy_map[i][j] = map[i][j];
            }
        }
    }

copy map과 copy fish에 지금 상태의 물고기와 맵을 저장해준다

여기서 내가 삽질 했던 것 중하나가

copy__fish[i].x = fish[i].x

copy_fish[i].y = fish[i].y 이런식으로 원소 하나하나씩 대입 시켜준게 아니라

xxxxxxxxxx
for(int i=1; i<=16; i++){
  copy_fish[i] = fish[i];
}

이렇게 객체를 통째로 주니 copy_fish와 fish가 같은 주소값을 가지고 있어 로직에 오류가 생겼다.

주의하자 . 객체는 값을 하나씩 넣어줘야 한다.

객체 뭉탱이로 복사를 하면 주소값을 원본과 공유한다

 

그리고 이제 물고기를 이동시켜준다

여기서 또 주의 할 게 있다.

물고기는 다른 물고기가 있는 칸 혹은 빈칸만 이동 할 수 있다.

여기서 빈칸/ 다른물고기가 있는 칸 을 구분해서 로직을 적어줘야한다.

map에서 상어에게 잡아먹힌칸은 0 / 상어가 있는칸은 -1 로 두니

둘의 로직을 하면 map에 저장된 물고기번호를 통해서 fish 배열에 접근을 하려고 하면

이미 잡아 먹힌 칸이라 0 이 되면 fish[0]으로 접근해 틀리게 된다.

 

전체코드

import java.io.*;
import java.util.*;
public class Main {
    static int dx[] = {100,-1,-1,0,1,1,1,0,-1};
    static int dy[] = {100,0,-1,-1,-1,0,1,1,1};
    static int map[][];
    static Fish[] fish;
    static int max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
​
        map = new int[5][5];
        fish = new Fish[17];
        for(int i=1; i<5; i++) {
​
            int map_input_cnt =0;
            String [] t = br.readLine().split(" ");
            for(int j=1; j<5; j++) {
                int a = Integer.parseInt(t[map_input_cnt]);
                int b = Integer.parseInt(t[map_input_cnt+1]);
                map_input_cnt+=2;
                map[i][j] =  a;
                fish[a] = new Fish(i,j,b,true);
            }
        }
        
        fish[map[1][1]].alive = false;
        int tmp_dir = fish[map[1][1]].dir;
        int tmp_fishNum = map[1][1];
        map[1][1] = -1;
        dfs(1,1,tmp_dir,tmp_fishNum);
        System.out.println(max);
    }
    public static void dfs(int sx, int sy, int sdir ,int sum) {
        max = Math.max(max, sum);
        
        int copy_map[][] = new int[5][5];
        Fish copy_fish[] = new Fish[17];
        for(int i=1; i<=16; i++) {
            copy_fish[i] = new Fish(0,0,0,true);
        }
        copy(copy_map,copy_fish);
        
        move_fish();
        
        for(int i=1; i<=3; i++) {
            int nx = sx+dx[sdir]*i;
            int ny = sy+dy[sdir]*i;
            if(!isRange(nx,ny) || map[nx][ny]==0) {
                continue;
            }
            int fish_num = map[nx][ny];
            int ndir = fish[fish_num].dir; // 이동할 위치에 있는 물고기 방향
    
            map[sx][sy] = 0;    // 원래 상어가 있던 위치 0으로 바꿔줌
            map[nx][ny] = -1;   // 상어가 이동할 위치에 -1로 해줌
            fish[fish_num].alive = false;   // 물고기 죽음 처리
            dfs(nx,ny,ndir,sum+fish_num);
            fish[fish_num].alive = true;    // 물고기 살음 처리
            map[nx][ny] = fish_num;
            map[sx][sy] = -1;
        }
        rollback(copy_map,copy_fish);
}
    public static void move_fish() {
        for(int i=1; i<=16; i++) {
            if(fish[i].alive == false) {
                continue;
            }
            boolean flag = false;
            int x = fish[i].x;
            int y = fish[i].y;
            int dir = fish[i].dir;
            
            int nx = x+dx[dir];
            int ny = y+dy[dir];
            if(isRange(nx,ny)  && map[nx][ny]!=-1) {
                flag = true;
                if(map[nx][ny]==0) {
                    dead_fish_change(i,x,y,nx,ny,dir);
                }
                else {
                    alive_fish_change(i,x,y,nx,ny,dir);
                }
            }   // isRange
            
            if(!flag) {
                int ndir = dir+1;
                if(ndir==9) {
                    ndir=1;
                }
                
                while(ndir!=dir) {
                    int tx = x+dx[ndir];
                    int ty = y+dy[ndir];
                    if(!isRange(tx,ty) || map[tx][ty]==-1) {
                        ndir++;
                        if(ndir==9) {
                            ndir=1;
                        }
                        continue;
                    }
                    else {
                        if(map[tx][ty]==0) {
                            dead_fish_change(i,x,y,tx,ty,ndir);
                            break;
                        }
                        else {
                            alive_fish_change(i,x,y,tx,ty,ndir);
                            break;
                        }
                    }
                }
            }   // !flag
        }   //for 
    }//move fish
    public static void dead_fish_change(int num,int x, int y, int nx, int ny, int dir) {
        // x,y는 원래위치 nx,ny는 움직이고 바뀐 위치
        fish[num].x = nx;
        fish[num].y = ny;
        fish[num].dir = dir;
        map[nx][ny] = num;
        map[x][y]=0;
    }
    public static void alive_fish_change(int num, int x, int y, int nx, int ny, int dir) {
        // x,y는 원래위치 nx,ny는 바뀐위치
        int other_fish = map[nx][ny];
        
        fish[num].x =nx;
        fish[num].y = ny;
        fish[num].dir = dir;
        
        fish[other_fish].x = x;
        fish[other_fish].y=y;
        
        map[x][y] = other_fish;
        map[nx][ny] = num;
    }
    public static void rollback(int copy_map[][], Fish copy_fish[]) {
        for(int i=1; i<=16; i++) {
            fish[i].x = copy_fish[i].x;
            fish[i].y = copy_fish[i].y;
            fish[i].dir = copy_fish[i].dir;
            fish[i].alive = copy_fish[i].alive;
        }
        for(int i=1; i<=4; i++) {
            for(int j=1; j<=4; j++) {
                map[i][j] = copy_map[i][j];
            }
        }
    }
    public static void copy(int copy_map[][], Fish copy_fish[]) {
        for(int i=1; i<=16; i++) {
            copy_fish[i].x = fish[i].x;
            copy_fish[i].y = fish[i].y;
            copy_fish[i].dir = fish[i].dir;
            copy_fish[i].alive = fish[i].alive;
        }
        for(int i=1; i<=4; i++) {
            for(int j=1; j<=4; j++) {
                copy_map[i][j] = map[i][j];
            }
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=1 && y>=1 && x<=4 && y<=4) {
            return true;
        }
        return false;
    }
}
class Fish{
    int x,y,dir;
    boolean alive;
    Fish(int x, int y, int dir,boolean alive){
        this.x=x;
        this.y=y;
        this.dir=dir;
        this.alive = alive;
    }
}