[백준]JAVA - 19236번: 청소년 상어

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

19236번: 청소년 상어

풀이

4 x 4 크기의 공간에 물고기 16마리가 존재한다. 상어가 먹을 수 있는 물고기 번호의 최댓값은?

 

위 문제의 로직은 아래와 같다.

 

1.  상어가 물고기를 잡아먹는다. 
2.  물고기가 이동한다.

 

1-1. 맨 처음 상어는 (0, 0)에 있는 물고기를 잡아먹는다.

1-2. 상어는 잡아먹은 물고기의 방향을 갖는다.

1-3. 방향을 유지한 채 범위 내에서 여러 개의 칸을 이동할 수 있다. (ex. 1칸, 2칸, 3칸)

 

2-1. 물고기의 번호가 작은 순서대로 본인의 방향으로 한 칸씩 이동한다.

2-2. 상어가 위치하는 곳으로는 이동할 수 없다.

2-3. 본인의 방향으로 이동할 수 없다면 이동할 수 있을 때까지 본인의 방향을 반시계방향으로  회전시킨다.

2-4. 이동할 수 있다면 그 위치에 있는 물고기와 자리를 변경한다.

 

로직을 잘 살펴보면 상어의 이동 위치에 따라서 여러 가지 경우의 수가 발생하는 걸 알 수 있다.

여러 가지 경우의 수에서 최댓값을 찾기 위해선 dfs를 이용해야 한다.

 

 

우선 물고기의 번호를 담는 2차원 배열 Map 과 물고기의 정보를 담는 Fish 객체 배열의 fishes 를 선언해서 입력했다.

Map[i][j] = num;
fishes[num] = new Fish(i, j, dir-1);

dfs를 이용하려면 임시 배열 Map을 사용해야 한다. 하나의 배열 Map을 사용하게 되면 값이 이상해질 수 있다. 그렇기 때문에 상어를 이동시킬 때마다 임시 배열 Map을 통해서 로직을 수행해야 한다. 

// 임시 배열 생성 후 복사
int[][] copyMap = new int[4][4];
Fish[] copyFish = new Fish[17];
        
for (int i=0; i<4; i++) {
    for (int j=0; j<4; j++) {
        copyMap[i][j] = Map[i][j];
    }
}
        
for (int i=1; i<17; i++) {
    copyFish[i] = new Fish(fishes[i].x, fishes[i].y, fishes[i].d);
}

배열을 복사할 때 주의할 점이 있다. 자바에서의 배열 복사는 얕은 복사와 깊은 복사가 존재한다. 자세한 내용은 아래 포스팅을 참고하면 좋다.

[JAVA] 얕은 복사와 깊은 복사에 대해서 알아보기

필자도 이것 때문에 답이 계속 이상하게 나왔는데, 객체 배열에서는 new 생성자를 통해서 생성 및 선언을 해야 깊은 복사가 이루어진다.

 

배열의 복사를 완료했다면 우선 상어가 이동한 위치에 물고기를 잡아먹는다. 필자는 잡아먹힌 물고기의 방향을 -1로 만들어줬다.

// 상어가 물고기를 잡아먹은 경우, 물고기의 방향을 -1로 선언
copyMap[x][y] = 0;
copyFish[Map[x][y]].d = -1;
        
for (int j=1; j<17; j++) {
    Fish now = copyFish[j];
            
    // 잡아먹힌 물고기의 경우
    if(now.d == -1) continue; 
            
    // 반시계 방향으로 돌면서 체크
    for (int k = 0; k < 8; k++) { 
        int nx = now.x + dx[(now.d+k)%8];
        int ny = now.y + dy[(now.d+k)%8];
                
        if (nx < 0 || ny < 0 || nx > 3 || ny > 3) continue;
        if (nx == x && ny == y) continue;

        if (copyMap[nx][ny] == 0) { 
            copyMap[nx][ny] = j;
            copyMap[now.x][now.y] = 0;
                    
            now.d = (now.d+k)%8;
            now.x = nx;
            now.y = ny;
        } else {
            int ind = copyMap[nx][ny];
            copyMap[nx][ny] = j;
            copyMap[now.x][now.y] = ind;
                    
            copyFish[ind].x = now.x;
            copyFish[ind].y = now.y;
                    
            now.d = (now.d+k)%8;
            now.x = nx;
            now.y = ny;
        }
                
        break;
    }
}

이후에 물고기의 번호 순서대로 이동시켜주면 된다. 물고기의 이동이 끝났다면 상어의 위치를 변경시켜준 후에 dfs를 돌려주면 된다. 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    static int ans = 0;
    
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
    
    public static class Fish {
        int x, y, d;
        
        public Fish (int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int[][] Map = new int[4][4];
        Fish[] fishes = new Fish[17];
        
        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());
                
                Map[i][j] = num;
                fishes[num] = new Fish(i, j, dir-1);
            }
        }
        
        dfs(Map, fishes, 0, 0, fishes[Map[0][0]].d, 0);
        System.out.println(ans);
    }
    
    public static void dfs (int[][] Map, Fish[] fishes, int x, int y, int d, int eat) {
        eat += Map[x][y];
        ans = Math.max(ans, eat);
        
        // 임시 배열 생성 후 복사
        int[][] copyMap = new int[4][4];
        Fish[] copyFish = new Fish[17];
        
        for (int i=0; i<4; i++) {
            for (int j=0; j<4; j++) {
                copyMap[i][j] = Map[i][j];
            }
        }
        
        for (int i=1; i<17; i++) {
            copyFish[i] = new Fish(fishes[i].x, fishes[i].y, fishes[i].d);
        }
        
        // 상어가 물고기를 잡아먹은 경우, 물고기의 방향을 -1로 선언
        copyMap[x][y] = 0;
        copyFish[Map[x][y]].d = -1;
        
        for (int j=1; j<17; j++) {
            Fish now = copyFish[j];
            
            // 잡아먹힌 물고기의 경우
            if(now.d == -1) continue; 
            
            // 반시계 방향으로 돌면서 체크
            for (int k = 0; k < 8; k++) { 
                int nx = now.x + dx[(now.d+k)%8];
                int ny = now.y + dy[(now.d+k)%8];
                
                if (nx < 0 || ny < 0 || nx > 3 || ny > 3) continue;
                if (nx == x && ny == y) continue;

                if (copyMap[nx][ny] == 0) { 
                    copyMap[nx][ny] = j;
                    copyMap[now.x][now.y] = 0;
                    
                    now.d = (now.d+k)%8;
                    now.x = nx;
                    now.y = ny;
                } else {
                    int ind = copyMap[nx][ny];
                    copyMap[nx][ny] = j;
                    copyMap[now.x][now.y] = ind;
                    
                    copyFish[ind].x = now.x;
                    copyFish[ind].y = now.y;
                    
                    now.d = (now.d+k)%8;
                    now.x = nx;
                    now.y = ny;
                }
                
                break;
            }
        }
        
        for (int i=1; i<4; i++) {
            int nx = x + dx[d]*i;
            int ny = y + dy[d]*i;
            
            if (nx < 0 || ny < 0 || nx > 3 || ny > 3) continue;
            if (copyMap[nx][ny] == 0) continue;
            
            dfs(copyMap, copyFish, nx, ny, copyFish[copyMap[nx][ny]].d, eat);
        }
    }
}