[백준 JAVA] 12100 : 2048 (Easy)

[백준 12100] 2048 (Easy) : https://www.acmicpc.net/problem/12100

---

문제 조건 정리

 

1. 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다.
2. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다.
3. 실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다.
4. 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.
   
   

---

 

입력 및 출력

 

1. 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다.
2. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다.
   0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다.
3. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
4. 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

---

문제를 풀면서

 

1. 일단 2048 게임을 한판 했다.
2. 블럭을 이동할 때, 새로운 블럭이 생기지 않아서 간단히 구현 가능하다고 생각했다.
3. 이동과 합체 과정을 한번에 진행하려고 하니 올바르게 작동하지 않았다.
4. 군데군데 0이 박힌 모습을 보고, 역시 프린트 찍어봐야한다고 생각했다.
5. 결국 이동, 합체, 이동 3단계로 나뉜 단계를 차례로 진행했다.
6. 왼쪽은 왼쪽에서부터 당겨야하고
   오른쪽은 오른쪽에서 당겨야한다는 점을 간과해서 또 고쳤다.

---

코드

 

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ12100 {

    static int n;
    static int maxValue = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());

        int[][] board = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            for (int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        simulate(board, 5);

        System.out.println(maxValue);

    }

    private static void simulate(int[][] board, int count) {
        if (count == 0) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    maxValue = Math.max(maxValue, board[i][j]);
                }
            }

            return;
        }

        for (int d = 0; d < 4; d++) {
            int[][] newBoard = copyBoard(board);
            newBoard = move(d, newBoard);
            simulate(newBoard, count - 1);
        }
    }

    private static int[][] move(int d, int[][] board) {
//        System.out.println("d = " + d);
//        System.out.println("d0 d1 d2 d3");
//        System.out.println("좌  우  상  하");
//        System.out.println();

        board = shift(d, board);
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.print(board[i][j] + " ");
//            }
//            System.out.println();
//        }
//        System.out.println();
        board = merge(d, board);
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.print(board[i][j] + " ");
//            }
//            System.out.println();
//        }
//        System.out.println();
        board = shift(d, board);
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.print(board[i][j] + " ");
//            }
//            System.out.println();
//        }
//        System.out.println();
//        System.out.println();
//        System.out.println();

        return board;
    }

    private static int[][] shift(int d, int[][] board) {

        if (d == 0) { // 좌로 밀착
            for (int i = 0; i < n; i++) {
                int[] temp = new int[n];
                int idx = 0;

                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 0) continue;
                    temp[idx++] = board[i][j];
                }
                board[i] = temp;
            }
        }

        if (d == 1) { // 우로 밀착
            for (int i = 0; i < n; i++) {
                int[] temp = new int[n];
                int idx = n - 1;

                for (int j = n - 1; j >= 0; j--) {
                    if (board[i][j] == 0) continue;
                    temp[idx--] = board[i][j];
                }
                board[i] = temp;
            }
        }
        if (d == 2) { // 위로 밀착
            for (int j = 0; j < n; j++) {
                int[] temp = new int[n];
                int idx = 0;

                for (int i = 0; i < n; i++) {
                    if (board[i][j] == 0) continue;
                    temp[idx++] = board[i][j];
                }
                for (int i = 0; i < n; i++) {
                    board[i][j] = temp[i];
                }
            }
        }
        if (d == 3) { // 아래로 밀착
            for (int j = 0; j < n; j++) {
                int[] temp = new int[n];
                int idx = n - 1;

                for (int i = n - 1; i >= 0; i--) {
                    if (board[i][j] == 0) continue;
                    temp[idx--] = board[i][j];
                }
                for (int i = 0; i < n; i++) {
                    board[i][j] = temp[i];
                }
            }
        }

        return board;
    }


    private static int[][] merge(int d, int[][] board) {
        if (d == 0) { // 좌
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n-1; j++) {
                    if (board[i][j] == 0) continue;
                    if (board[i][j] == board[i][j + 1]) {
                        board[i][j] *= 2;
                        board[i][j+1] = 0;
                        j++;
                    }
                }
            }
            return board;
        }
        if (d == 1) { // 우
            for (int i = 0; i < n; i++) {
                for (int j = n-1; j >0; j--) {
                    if (board[i][j] == 0) continue;
                    if (board[i][j] == board[i][j - 1]) {
                        board[i][j] *= 2;
                        board[i][j-1] = 0;
                        j--;
                    }
                }
            }
            return board;
        }
        if (d == 2) { // 상
            for (int j = 0; j < n; j++) {
                for (int i = 0; i < n - 1; i++) {
                    if (board[i][j] == 0) continue;
                    if (board[i][j] == board[i + 1][j]) {
                        board[i][j] *= 2;
                        board[i + 1][j] = 0;
                        i++;
                    }
                }
            }
            return board;
        }
        if (d == 3) { // 하
            for (int j = 0; j < n; j++) {
                for (int i = n - 1; i > 0; i--) {
                    if (board[i][j] == 0) continue;
                    if (board[i][j] == board[i - 1][j]) {
                        board[i][j] *= 2;
                        board[i - 1][j] = 0;
                        i--;
                    }
                }
            }
            return board;
        }


        return board;
    }

    private static int[][] copyBoard(int[][] board) {
        int[][] newBoard = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                newBoard[i][j] = board[i][j];
            }
        }

        return newBoard;
    }
}

 

---

문제를 풀고 난 후

 

백트래킹이 기반이 되는 시뮬레이션 문제를 풀다보니 백트래킹은 문제가 아닌 것을 이제야 알겠다.

문제를 해결하기 위해서 어떻게 접근해야하는지 더욱 깊게 생각해야했다.

이런 문제들을 풀 때, 최대한 함수는 쪼개고 단순하게, 그리고 아직까지는 디버깅을 위해서 출력을 찍어보는 습관이 필요할 것 같다.