[백준] 12100번 / Java / 2048 (Easy)

문제 https://www.acmicpc.net/problem/12100

간단히 하면, 블록을 5번 움직여서 만들어지는 블록 중 값이 가장 큰 블록의 값을 출력하는 문제

 

하지만 알고 넘어가야 할 부분이 있다!

 

1. 상하좌우로 이동하는데 이동했을 때 같은 값이 만나면 합쳐진다

2. 이동시 전체 블록이 모두 이동한다.

3. 연쇄작용하면서 합칠 필요 없다 (문제의 그림12 1행을 보면 2끼리 합쳐서 4가 되지만 그림 13에서는 44로 나타내지 8로까지 합치진 않았다)

4. 같은 블록이 3개면, 이동한 방향을 우선으로 합한다. 3번에서 애매해지는 부분을 여기서 확실히 한 것 같다.

 

 

나의 실수

재정의/추상화는 잘 했지만 이번에도 계획을 제대로 세우지 않고 문제를 풀었다

내가 유독 반복하는 실수가 있는데, 여러 조건을 한 번에 처리하려고 하는 버릇이다

이 문제의 경우

1. 이동하는 방향에 따라 빈 칸을 채워준다

2. 이동하는 방향에 맞게 인접한 값들 중 같은 값을 더한다. (이동방향 순으로 첫 번째에는 더한 값을 두 번째는 0을 대입)

3. 2번 과정으로 생긴 빈 칸을 다시 채워준다

이 복잡한 과정을 for문에서 한번에 하려고 하니까 시간이 오래 걸렸다 ㅠㅠ

내가 너무 미련하게 짜고 있단 것을 깨닫고 1,3번 기능을 fillBlank함수로, 2번을 moveBlock함수로 분리해서 구현했다.

 

또하나 실수한 것!!

이건 자바를 하는 사람이라면 간과하기 쉬운 점인데..

바로 깊은 복사와 얕은 복사다..

나는 계속 재귀를 타는 동안 얕은 복사를 사용해서 한번 변경된 board 배열을 가지고 계속해서 써먹어서 원하는 결과를  못 뽑아냈다

예전에도 했던 실수여서 원인 파악하자마자 금방 고치긴 했지만.. 처음에 원인 파악도 못해서 헤맨 시간 생각하면 이런 실수는 하지 않아야 한다 ㅠㅠ

 

 

코드를 보려면 아래 '더보기' 클릭

/**
 * 2시간 53분........................
 */
public class _12100_2048Easy{
    static int answer = 0;

    static void recursion(int k, int[][] board){
        // 기저
        if (k == 5) {
            // board에서 가장 큰 블록 값 찾기
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board.length; j++) {
                    answer = Math.max(answer, board[i][j]);
                }
            }
            return;
        }

        System.out.println(k+"번째");
        recursion(k + 1, moveBlock(deepCopy(board), 1));
        recursion(k + 1, moveBlock(deepCopy(board), 2));
        recursion(k + 1, moveBlock(deepCopy(board), 3));
        recursion(k + 1, moveBlock(deepCopy(board), 4));
    }

    static int[][] deepCopy(int[][] ary) {
        int[][] ret = new int[ary.length][ary.length];
        int i = 0;
        for (int[] _ary : ary) {
            System.arraycopy(_ary, 0, ret[i++], 0, ret.length);
        }
        return ret;
    }

    static void printBoard(int[][] board, int dir){
        System.out.println("<" + dir + ">");
        for (int[] bo : board) {
            for (int b : bo) {
                System.out.print(b + " ");
            }
            System.out.println();
        }
        System.out.println("-------------------------");
    }

    static int[][] moveBlock(int[][] board, int dir) {
        board = fillBlank(board, dir);
        switch (dir) {
            case 1: // 위아래로 같은 것들 더해주기
                for (int i = 0; i < board.length - 1; i++)
                    for (int j = 0; j < board.length; j++) {
                        int move = i + 1;
                        if (board[i][j] == board[move][j]) {
                            board[i][j] += board[move][j];
                            board[move][j] = 0;
                        }
                    }
                break;
            case 2: // 아래위로 같은 것들 더해주기
                for (int i = board.length - 1; i >= 1; i--)
                    for (int j = 0; j < board.length; j++) {
                        int move = i - 1;
                        if (board[i][j] == board[move][j]) {
                            board[i][j] += board[move][j];
                            board[move][j] = 0;
                        }
                    }
                break;
            case 3: // 왼->오로 같은 것들 더해주기
                for (int i = 0; i < board.length; i++)
                    for (int j = 0; j < board.length - 1; j++) {
                        int move = j + 1;
                        if (board[i][move] == board[i][j]) {
                            board[i][j] += board[i][move];
                            board[i][move] = 0;
                        }
                    }
                break;
            case 4:
                for (int i = 0; i < board.length; i++)
                    for (int j = board.length - 1; j > 0; j--) {
                        // 오른쪽으로 이동이므로 왼쪽 방향에서 0이 아닌 블럭 찾아서 이동시키기
                        int move = j - 1;
                        if (board[i][move] == board[i][j]) {
                            board[i][j] += board[i][move];
                            board[i][move] = 0;
                        }
                    }
                break;
        }
        return fillBlank(board, dir);
    }

    static int[][] fillBlank(int[][] board, int dir) {
        switch (dir) {
            case 1: // 위로 이동
                for (int i = 0; i < board.length; i++)
                    for (int j = 0; j < board.length; j++) {
                        if (board[i][j] == 0) {
                            // 위로 이동이므로 아래방향에서 0이 아닌 블럭 찾아서 이동시키기
                            int move = i + 1;
                            while (move < board.length) {
                                if (board[move][j] != 0) {
                                    board[i][j] = board[move][j];
                                    board[move][j] = 0;
                                    break;
                                }
                                move++;
                            }
                        }
                    }
                break;
            case 2: // 아래로 이동
                for (int i = board.length - 1; i >= 0; i--)
                    for (int j = 0; j < board.length; j++) {
                        // 아래로 이동이므로 위 방향에서 0이 아닌 블럭 찾아서 이동시키기
                        if (board[i][j] == 0) {
                            int move = i - 1;
                            while (move >= 0) {
                                if (board[move][j] != 0) {
                                    board[i][j] = board[move][j];
                                    board[move][j] = 0;
                                    break;
                                }
                                move--;
                            }
                        }
                    }
                break;
            case 3: // 왼쪽으로 이동
                for (int i = 0; i < board.length; i++)
                    for (int j = 0; j < board.length; j++) {
                        // 왼쪽으로 이동이므로 오른쪽 방향에서 0이 아닌 블럭 찾아서 이동시키기
                        if (board[i][j] == 0) {
                            int move = j + 1;
                            while (move < board.length) {
                                if (board[i][move] != 0) {
                                    board[i][j] = board[i][move];
                                    board[i][move] = 0;
                                    break;
                                }
                                move++;
                            }
                        }
                    }
                break;
            case 4:
                for (int i = 0; i < board.length; i++)
                    for (int j = board.length - 1; j > 0; j--) {
                        // 오른쪽으로 이동이므로 왼쪽 방향에서 0이 아닌 블럭 찾아서 이동시키기
                        if (board[i][j] == 0) {
                            int move = j - 1;
                            while (move >= 0) {
                                if (board[i][move] != 0) {
                                    board[i][j] = board[i][move];
                                    board[i][move] = 0;
                                    break;
                                }
                                move--;
                            }
                        }
                    }
                break;
        }
        printBoard(board, dir);
        return board;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] board = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        recursion(0, board);
        System.out.println(answer);
    }
}