[Algorithm] 백준_청소년 상어_19236번 (JAVA) 🐟

📝문제

티어: 골드1 

 

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

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

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

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

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

 

💡풀이

문제 유형

구현
시뮬레이션
백트래킹

 

걸린 시간

3시간???ㅜㅜ

 

풀이 방법 도출

1. 물고기 번호 배열(num)과 물고기 방향 배열(dir)을 따로 입력 받았다. 
2. 상어가 (0,0)에 들어간다. 기존 (0,0)의 물고기 번호를 저장해두고 (0,0) 자리에 0으로 초기화해 주어 물고기가 없는 자리임을 식별할 수 있게 해준다.
3. 현재 상어 위치를 기준으로 dfs를 돌린다. 위치와 상어의 방향, 물고기 번호 배열과 물고기 방향 배열을 같이 넘겨준다.
4. dfs(0, 0, start, dir[0][0], num, dir);
5. 모든 경우를 탐색 해야하므로 배열을 깊은 복사 해주어야한다.
   int[][] tempNum = copyArray(num);
   int[][] tempDir = copyArray(dir);
6. 복사된 배열로 물고기를 1번부터 16번까지 이동시켜준다. moveFish(x, y, tempNum, tempDir);
7. 호출된 moveFish에서는 물고기 번호를 찾고 그 번호의 위치를 저장해준다. fx = i, fy = j
   for (int i = 0; i < 4; i++) {
       for (int j = 0; j < 4; j++) {
           if (num[i][j] == fishNum) {
               fx = i;
               fy = j;
               break;
           }
       }
   }
8. 물고기의 회전은 반시계 방향으로 45도씩 돌아가므로 정적 변수로 선언해주었다.
   static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};
9. 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시켜야하므로 idx = (idx + 1) % 8;로 계산해주고 총 8번의 계산까지 반복될 수 있도록 하였다.
10. 이동 가능한 칸이라면 위치를 서로 바꿔주고 다시 7번으로 돌아가 반복한다.
11. 물고기 이동이 끝나면 상어의 이동이 시작된다.
12. 상어의 방향을 기준으로 모든 경우의 수가 필요하므로 배열을 또 한 번 깊은 복사 해주어 dfs로 복사된 배열을 넘겨주었다.

// 물고기 이동이 모두 끝나면 상어 이동
// 한 번에 여러 개의 칸을 이동할 수 있다.
// 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다.
// 물고기가 없는 칸으로는 이동할 수 없다.
// 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다.

// 물고기는 번호가 작은 물고기부터 순서대로 이동한다.
// 한 칸 이동 가능, 빈 칸과 다른 물고기가 있는 칸
// 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킴
// 모든 물고기가 이동

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

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

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

        int[][] num = new int[4][4];
        int[][] dir = new int[4][4];

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

        //1.상어가 (0,0)에 들어감
        int start = num[0][0];
        num[0][0] = 0;
        dfs(0, 0, start, dir[0][0], num, dir);//상어 X위치, 상어 Y위치, 상어 방향, sum

        System.out.println(answer);
    }

    public static void dfs(int x, int y, int sum, int sharkDir, int[][] num, int[][] dir) {
        answer = Math.max(answer, sum);

        int[][] tempNum = copyArray(num);
        int[][] tempDir = copyArray(dir);

        //2. 물고기 이동
        moveFish(x, y, tempNum, tempDir);

        //3. 상어 이동
        for (int i = 1; i < 4; i++) {
            int nx = x + dx[sharkDir] * i;
            int ny = y + dy[sharkDir] * i;
            if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && tempNum[nx][ny] != 0) {// 물고기가 없는 칸으로는 이동할 수 없다.
                int[][] nexNum = copyArray(tempNum);
                int[][] nextDir = copyArray(tempDir);

                int nextFish = nexNum[nx][ny];     // 먹을 물고기 번호

                nexNum[nx][ny] = 0;                // 상어가 먹음 → 빈칸 처리

                dfs(nx, ny, sum + nextFish, nextDir[nx][ny], nexNum, nextDir);
            }
        }
    }

    public static int[][] copyArray(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;
    }

    public static void moveFish(int x, int y, int[][] num, int[][] dir) {
        int fishNum = 0;
        //2.물고기 이동
        while (fishNum <= 16) {
            fishNum++;
            int fx = -1;
            int fy = -1;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if (num[i][j] == fishNum) {
                        fx = i;
                        fy = j;
                        break;
                    }
                }
            }

            //해당 번호의 물고기가 없음
            if(fx == -1 && fy == -1) continue;

            int idx = dir[fx][fy];
            for (int i = 0; i < 8; i++) {//만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다.
                //물고기 방향으로 전진
                int nx = fx + dx[idx];
                int ny = fy + dy[idx];

                //이동할 수 있는 칸이라면
                if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && !(nx == x && ny == y)) {

                    //그 칸에 있는 물고기와 위치 바꾸기
                    int temp = num[fx][fy];

                    num[fx][fy] = num[nx][ny];
                    num[nx][ny] = temp;

                    dir[fx][fy] = dir[nx][ny];
                    dir[nx][ny] = idx;
                    break;
                }
                //이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다.
                idx = (idx + 1) % 8;

            }
        }
    }
}

 

🤔Review

풀다가 마우스 던질뻔.. 왜이렇게 어렵지