[BOJ 12100] 2048 (Easy) (Java)

BOJ 12100 2028 (Easy)

난이도 : 골드 2

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

12100번: 2048 (Easy)

 

전략

각 라운드마다 위 / 아래 / 왼쪽 / 오른쪽 4방향으로 이동시킬 수 있다.

문제에서 최대 5번으로 제한을 뒀으므로 모든 경우의 수는 4^5 = 1024이다. 

브루트포스로 가능하기 때문에 구현에 초점을 둬서 진행한다.

 

시행착오

셀 충돌하고 병합하는 과정을 구현하면서 루프의 범위가 잘못된 경우가 있었다.

이 문제에서 많이들 놓치는 조건인 '한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없다'도 조심해야한다.

탐색을 하기 전에 Board를 이동시켰을 때 결과가 주어진 예시와 모두 일치하도록 요구사항을 먼저 만족시키면서 구현하였다.

 

코드

        // 1st -> 2nd -> 3rd ===merge==> 1st 2nd 3rd
        private static int[] merge(int[] prev) {
            int n = prev.length;
            if (n == 1)
                return prev;

            int[] merged = new int[n];
            System.arraycopy(prev, 0, merged, 0, n);

            for (int i = n - 1; i >= 0; i--) {
                for (int j = i - 1; j >= 0; j--) {
                    if (merged[j] == 0) continue;
                    if (merged[i] == merged[j]) {
                        merged[i] <<= 1;
                        merged[j] = 0;
                    }
                    break;
                }
            }
            shift(merged, n);

            return merged;
        }

        // 1st <- 2nd <- 3rd ===merge==> 1st 2nd 3rd
        private static int[] mergeInverse(int[] prev) {
            int n = prev.length;
            if (n == 1)
                return prev;

            int[] merged = new int[n];
            System.arraycopy(prev, 0, merged, 0, n);

            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (merged[j] == 0) continue;
                    if (merged[i] == merged[j]) {
                        merged[i] <<= 1;
                        merged[j] = 0;
                    }
                    break;
                }
            }
            shiftInverse(merged, n);

            return merged;
        }

 

한 줄 단위로 이동하도록 구현하였다.

순방향 (moveRight, moveDown) -> merge

역방향 (moveLeft, moveUp) -> mergeInverse

이렇게 따로 구현하였다.

 

이웃된 칸 (중간에 비어있거나 바로 붙어있는 두 칸)의 수가 같다면 방향에 맞는 위치에 *2를 하고 나머지 칸은 0으로 만든다.

모두 병합이 완료되면 빈칸 없이 밀어 붙이도록 shift를 한다.

 

        private static void shift(int[] merged, int n) {
            for (int i = n - 2; i >= 0; i--) {
                for (int j = n - 1; j > i; j--) {
                    if (merged[j] == 0) {
                        merged[j] = merged[i];
                        merged[i] = 0;
                    }
                }
            }
        }

        private static void shiftInverse(int[] merged, int n) {
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (merged[j] == 0) {
                        merged[j] = merged[i];
                        merged[i] = 0;
                    }
                }
            }
        }

shift는 간단하다. 숫자가 있는 칸 기준으로 자기보다 앞에 0이 있으면 가장 앞의 0의 위치로 스왑한다.

 

이제 주요 기능들이 다 완성되었으니 네 가지 경우의 move만 있으면 된다.

 

        public Board moveLeft() {
            int n = this.cells.length;
            Board board = new Board(this);
            for (int i = 0; i < n; i++) {
                int[] merged = mergeInverse(board.cells[i]);
                board.cells[i] = merged;
            }
            return board;
        }

        public Board moveRight() {
            int n = this.cells.length;
            Board board = new Board(this);
            for (int i = 0; i < n; i++) {
                int[] merged = merge(board.cells[i]);
                board.cells[i] = merged;
            }
            return board;
        }

        public Board moveDown() {
            int n = this.cells.length;
            Board board = new Board(this);
            for (int i = 0; i < n; i++) {
                int[] prev = new int[n];

                for (int j = 0; j < n; j++) {
                    prev[j] = board.cells[j][i];
                }
                int[] merged = merge(prev);

                for (int j = 0; j < n; j++) {
                    board.cells[j][i] = merged[j];
                }
            }
            return board;
        }

        public Board moveUp() {
            int n = this.cells.length;
            Board board = new Board(this);
            for (int i = 0; i < n; i++) {
                int[] prev = new int[n];

                for (int j = 0; j < n; j++) {
                    prev[j] = board.cells[j][i];
                }
                int[] merged = mergeInverse(prev);

                for (int j = 0; j < n; j++) {
                    board.cells[j][i] = merged[j];
                }
            }
            return board;
        }

moveLeft, moveRight는 그냥 바로 merge를 쓰면 된다. (행 단위이므로)

moveUp, moveDown은 2차원 배열의 각 행에서 원하는 열을 뽑아서 진행하는 과정이 추가된다.

 

    static class Board {
        final int[][] cells;

        Board(int n) {
            this.cells = new int[n][n];
        }

        Board(Board board) {
            int n = board.cells.length;
            this.cells = new int[n][n];
            for (int i = 0; i < n; i++) {
                System.arraycopy(board.cells[i], 0, this.cells[i], 0, n);
            }
        }

        public int getMax() {
            int max = 0;
            for (int i = 0; i < cells.length; i++) {
                for (int j = 0; j < cells[i].length; j++) {
                    max = Math.max(cells[i][j], max);
                }
            }
            return max;
        }
        
        ...
    }

위의 모든 기능은 Board 클래스 단위로 제공한다.

move 메소드들은 Board를 수정하지 않고 새로운 객체를 반환한다. 이는 백트래킹 과정을 쉽게 하기 위함이다.

 

     static int search(Board board, int count) {
        if (count == 0) return board.getMax();

        int[] results = new int[5];
        results[0] = search(board.moveLeft(), count - 1);
        results[1] = search(board.moveRight(), count - 1);
        results[2] = search(board.moveUp(), count - 1);
        results[3] = search(board.moveDown(), count - 1);
        results[4] = board.getMax();

        int max = 0;
        for (int cnt : results)
            max = Math.max(max, cnt);

        return max;
     }

 

탐색은 브루트포스이므로 간단하다.

재귀로 모든 경우의 수를 탐색하도록 하였다.

이 때 주의할 점으로 최대 5번 이동하였을 때의 최대이므로 현재 상태의 최댓값도 함께 비교해줘야 한다.

 

main 메소드에서는

System.out.println(search(board, 5));

이렇게 호출하면 솔루션이 완성된다.

 

깨달은 점

코딩테스트에서 200라인짜리 구현 문제가 막상 펼쳐지면 아찔할 것 같다..

요즘에 구현이 대세인데 이렇게 이동/회전하는 문제들을 조금 더 풀어봐야겠다.

 

그래도 성취감은 다른 문제들보다 짜릿한 것 같다!