[백준 12100 : JAVA] 2048 (Easy)

문제

---

2048 게임은 4x4 크기의 보드에서 혼자 즐기는 재미있는 게임이다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다.)

[그림 1] 좌측의 보드판을 좌측으로 이동시켰을 경우

 

게임의 룰은 다음과 같다.

1. 보드판은 상, 하, 좌, 우로 이동할 수 있다.
2. 앞의 블록과 값이 같다면 두 값을 더한 하나의 블록으로 합쳐진다.
3. 한 방향으로의 이동에서 각각의 블록은 한 번씩만 합쳐질 수 있다.

 

이 문제에서 다루는 2048 게임은 보드의 크기가 NxN이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 보드의 크기 N($1 le N le 20$)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이 외의 값은 모두 블록을 나타낸다. 블록에 쓰여있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

 

출력

---

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

 

풀이

---

이 문제는 크게 두 가지를 요구합니다.

1. 중복 순열을 구할 수 있는가?
2. 게임을 시뮬레이션할 수 있는가?

 

먼저, 최대 5번의 상하좌우 이동으로 얻을 수 있는 가장 큰 블록을 구해야하기 때문에 상하좌우 4개에 대해서 중복 순열로 5개를 뽑습니다.

최대 5번이기 때문에 3번만에도 최대값이 나올 수 있지만, 별도의 처리를 해줄 필요는 없습니다. 아래처럼 5개를 뽑았다 해보겠습니다.

[상 상 하 하 좌]   <-- 상을 연속해서 두번하나 한번하나 결과는 동일합니다. 따라서, [상 하 좌] 총 3번 이동한 것과 같습니다. 따라서, 5개의 중복 순열을 백트래킹을 이용하여 구해줍니다.

 

두 번째로 게임을 시뮬레이션하는 것은 반복문을 이용하여 이동하고자 하는 방향으로 계속 한 칸씩 이동시켜주게끔 구현하였습니다.

 

코드

---

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

public class Main {

    private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private static int N, result;
    private static Node[][] board;

    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(in.readLine());
        board = new Node[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = new Node(Integer.parseInt(st.nextToken()), false);
            }
        }

        // 중복 순열
        multisetPermutation(0, "");
        System.out.println(result);
    }

    private static void multisetPermutation(int depth, String str) throws CloneNotSupportedException {
        if (depth == 5) {
//            Node[][] tmpBoard = board.clone();
            Node[][] tmpBoard = new Node[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    tmpBoard[i][j] = board[i][j].clone();
                }
            }

            for (int i = 0; i < 5; i++) {
                play(tmpBoard, str.charAt(i));
                initCombineCnt(tmpBoard);
            }
            result = Math.max(result, findMaxBlock(tmpBoard));
            return;
        }

        for (int i = 0; i < 4; i++) {
            multisetPermutation(depth + 1, str + i);
        }
    }

    private static int findMaxBlock(Node[][] board) {
        int maxVal = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                maxVal = Math.max(maxVal, board[i][j].val);
            }
        }
        return maxVal;
    }

    private static void initCombineCnt(Node[][] board) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j].isCombine = false;
            }
        }
    }

    private static void play(Node[][] board, char c) {
        if (c == '0') { // 상
            for (int x = 0; x < N; x++) {
                boolean move = true;
                while (move) {
                    move = false;
                    for (int y = 1; y < N; y++) {
                        if (board[y - 1][x].val == 0 && board[y][x].val != 0) {
                            board[y - 1][x].val = board[y][x].val;
                            board[y - 1][x].isCombine = board[y][x].isCombine;
                            board[y][x].init();
                            move = true;
                        } else if (board[y - 1][x].val == board[y][x].val) {
                            if (!board[y - 1][x].isCombine && !board[y][x].isCombine) {
                                board[y - 1][x].val += board[y][x].val;
                                board[y - 1][x].isCombine = true;
                                board[y][x].init();
                                move = true;
                            }
                        }
                    }
                }
            }
        } else if (c == '1') { // 하
            for (int x = 0; x < N; x++) {
                boolean move = true;
                while (move) {
                    move = false;
                    for (int y = N - 2; y >= 0; y--) {
                        if (board[y + 1][x].val == 0 && board[y][x].val != 0) {
                            board[y + 1][x].val = board[y][x].val;
                            board[y + 1][x].isCombine = board[y][x].isCombine;
                            board[y][x].init();
                            move = true;
                        } else if (board[y + 1][x].val == board[y][x].val) {
                            if (!board[y + 1][x].isCombine && !board[y][x].isCombine) {
                                board[y + 1][x].val *= 2;
                                board[y + 1][x].isCombine = true;
                                board[y][x].init();
                                move = true;
                            }
                        }
                    }
                }
            }
        } else if (c == '2') { // 좌
            for (int y = 0; y < N; y++) {
                boolean move = true;
                while (move) {
                    move = false;
                    for (int x = 1; x < N; x++) {
                        if (board[y][x - 1].val == 0 && board[y][x].val != 0) {
                            board[y][x - 1].val = board[y][x].val;
                            board[y][x - 1].isCombine = board[y][x].isCombine;
                            board[y][x].init();
                            move = true;
                        } else if (board[y][x - 1].val == board[y][x].val) {
                            if (!board[y][x - 1].isCombine && !board[y][x].isCombine) {
                                board[y][x - 1].val *= 2;
                                board[y][x - 1].isCombine = true;
                                board[y][x].init();
                                move = true;
                            }
                        }
                    }
                }
            }
        } else if (c == '3') { // 우
            for (int y = 0; y < N; y++) {
                boolean move = true;
                while (move) {
                    move = false;
                    for (int x = N - 2; x >= 0; x--) {
                        if (board[y][x + 1].val == 0 && board[y][x].val != 0) {
                            board[y][x + 1].val = board[y][x].val;
                            board[y][x + 1].isCombine = board[y][x].isCombine;
                            board[y][x].init();
                            move = true;
                        } else if (board[y][x + 1].val == board[y][x].val) {
                            if (!board[y][x + 1].isCombine && !board[y][x].isCombine) {
                                board[y][x + 1].val *= 2;
                                board[y][x + 1].isCombine = true;
                                board[y][x].init();
                                move = true;
                            }
                        }
                    }
                }
            }
        }
    }

    private static class Node implements Cloneable {
        int val;
        boolean isCombine;

        public Node(int val, boolean isCombine) {
            this.val = val;
            this.isCombine = isCombine;
        }

        @Override
        protected Node clone() throws CloneNotSupportedException {
//            return (Node) super.clone();
            return new Node(this.val, false);
        }

        private void init() {
            this.val = 0;
            this.isCombine = false;
        }
    }
}