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

문제

www.acmicpc.net/problem/19236

19236번: 청소년 상어

문제해결방법

이 문제는 DFS를 통해 상어의 모든 경로를 구해주었다.

DFS로 상어의 경로를 탐색하면서 4X4X2 크기의 공간에 현재 상어, 물고기, 빈 공간과 방향을 가지고 다녔고

17X2 크기의 공간에 물고기들의 현재 위치를 담아서 물고기들이 이동하는걸 빠르게 구현해주었다.

* 배열을 복사할 때 clone()을 하면 deep copy가 되는 줄 알았는데 아니여서 그냥 같은 크기의 배열을 만들고 값을 복사해주었다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main19236_청소년상어 {
 
    public static int max = 0;
    public static int[][] dir = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};
    public static int[][] fish = new int[17][2];
    public static int[][][] map = new int[4][4][2];
        
    public static void dfs(int x, int y, int[][][] map, int[][] fish, int sum) {
        // 상어가 물고기를 먹음
        sum += map[x][y][0];
        int sharkDir = map[x][y][1];
        fish[map[x][y][0]][0] = -1;
        fish[map[x][y][0]][1] = -1;
        map[x][y][0] = -1;
        map[x][y][1] = -1;
        // 물고기 이동
        for(int i=1; i<=16; i++) {
            if(fish[i][0]!=-1) {
                int curX = fish[i][0];
                int curY = fish[i][1];
                int curDir = map[curX][curY][1];
                for(int d=0; d<dir.length; d++) {
                    int nextDir = (curDir+d)%dir.length;
                    int nextX = curX + dir[nextDir][0];
                    int nextY = curY + dir[nextDir][1];
                    if(nextX>=0 && nextX<4 && nextY>=0 && nextY<4 && map[nextX][nextY][0]!=-1) {
                        fish[i][0] = nextX;
                        fish[i][1] = nextY;
                        if(map[nextX][nextY][0]!=0) {
                            fish[map[nextX][nextY][0]][0] = curX;
                            fish[map[nextX][nextY][0]][1] = curY;
                        }
                        int temp = map[nextX][nextY][0];
                        map[nextX][nextY][0] = map[curX][curY][0];
                        map[curX][curY][0] = temp;
                        temp = map[nextX][nextY][1];
                        map[nextX][nextY][1] = nextDir;
                        map[curX][curY][1] = temp;
                        break;
                    }
                }
            }
        }
        // 상어가 다음 위치로 이동
        int nX = x+dir[sharkDir][0], nY = y+dir[sharkDir][1];
        while(nX>=0 && nX<4 && nY>=0 && nY<4) {
            if(map[nX][nY][0]>0) {
                int[][][] tempMap = new int[4][4][2];
                int[][] tempFish = new int[17][2];
                for(int i=0; i<map.length; i++) {
                    for(int j=0; j<map[i].length; j++) {
                        for(int k=0; k<map[i][j].length; k++) tempMap[i][j][k] = map[i][j][k];
                    }
                }
                for(int i=0; i<fish.length; i++) {
                    for(int j=0; j<fish[i].length; j++) tempFish[i][j] = fish[i][j];
                }
                tempMap[x][y][0] = 0;
                tempMap[x][y][1] = -1;
                dfs(nX, nY, tempMap, tempFish, sum);
            }
            nX += dir[sharkDir][0];
            nY += dir[sharkDir][1];
        }
        if(max<sum) max = sum;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int i=1; i<fish.length; i++) {
            fish[i][0] = -1;
            fish[i][1] = -1;
        }
        for(int i=0; i<map.length; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<map[i].length; j++) {
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                map[i][j][0] = a;
                map[i][j][1] = b-1;
                fish[a][0] = i;
                fish[a][1] = j;
            }
        }
        dfs(0, 0, map, fish, 0);
        System.out.println(max);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.