[코드트리] 2048 게임

2048 게임

문제

2048게임은 4 * 4 격자 안에서 이루어지는 게임입니다. 이 2048 게임에서는 상하좌우 중 한 방향을 정하게 되면, 모든 숫자들이 해당 방향으로 전부 밀리게 됩니다.

예를 들어 다음 판에서 밑으로 방향을 정하게 되면, 다음과 같이 아래로 중력이 작용한 이후의 결과를 얻게 됩니다.

하지만 2048 게임에서는 같은 숫자끼리 만나게 되는 경우 두 숫자가 합쳐지게 됩니다. 다음의 경우 아래로 움직이는 예를 보면 숫자 2 두 개가 합쳐서 숫자 4가 됩니다.

또한, 단 한 번의 중력작용으로 이미 합쳐진 숫자가 연쇄적으로 합쳐지진 않습니다. 다음의 경우 아래로 움직이는 예를 보면 숫자 2 두 개가 이미 한번 합쳐져 4가 되었기 때문에, 위의 4와 다시 합쳐지진 않습니다.

그리고 세 개 이상의 같은 숫자가 중력작용 방향으로 놓여 있으면, 중력에 의해 부딪히게 될 벽(바닥)에서 가까운 숫자부터 두 개씩만 합쳐집니다. 즉, 서너개 이상의 숫자가 하나로 합쳐질 순 없고 아래 예시처럼 바닥에 가까운 순서대로 한 쌍씩 짝을 이뤄 합쳐집니다. 다음 예시는 아래로 중력이 작용해서 숫자 2 네개가 4 두개로 합쳐진 것입니다.

2, 4, 8, 16 등 2의 거듭제곱꼴로 나타나는 2 이상 2048 이하의 숫자들로 구성된 4 * 4 격자 판이 주어졌을 때, 5번 움직인 이후에 격자판에서 가장 큰 값의 최댓값을 구하는 프로그램을 작성해보세요.

예를 들어 다음 격자의 경우 위, 아래, 왼쪽, 오른쪽으로 이동하게 되면, 각각 아래 그림과 같은 결과들을 얻을 수 있습니다.

격자 판이 주어질 때, 5번 이동하여 얻을 수 있는 가장 큰 블록의 수를 구하세요.

입력 형식

첫째 줄에는 격자의 크기 n이 주어집니다.

둘째 줄부터 (n+1)번째 줄까지 초기 상태가 주어집니다.

격자의 빈칸은 0으로 나타내며, 블록들은 2의 거듭제곱 형태로 나타납니다.

1 ≤ n ≤ 20

2 ≤ (블록의 값) ≤ 1024

블록은 적어도 하나 이상 주어진다고 가정해도 좋습니다.

출력 형식

격자를 5번 이동해서 얻을 수 있는 가장 큰 블록의 수를 출력하세요.

풀이

위, 아래, 왼쪽, 오른쪽으로 움직이는 것을 구현한 다음
백트레킹을 이용해 모든 경우의 수를 확인하여 최댓값을 구한다.

코드

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

public class Main{

    static int ans = 0;

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

        int[][] graph = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        int[] dir = new int[5];
        backTracking(0, dir, graph);
        System.out.println(ans);
    }

    static void backTracking(int depth, int[] arr, int[][] graph){
        if (depth == 5) {
            int[][] temp = graphCopy(graph);
            for (int i = 0; i < 5; i++) {
                temp = move(temp, arr[i]);
            }

            ans = Math.max(ans, getMaxNum(temp));

            return;
        }
        for (int i = 0; i < 4; i++) {
            arr[depth] = i;
            backTracking(depth + 1, arr, graph);
        }
    }

    static int getMaxNum(int[][] graph){
        int n = graph.length;
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, graph[i][j]);
            }
        }

        return max;
    }

    static int[][] graphCopy(int[][] graph){
        int[][] ret = new int[graph.length][graph.length];
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                ret[i][j] = graph[i][j];
            }
        }
        return ret;
    }

    // dir 0 : 우, 1 : 하, 2: 좌, 3: 상
    static int[][] move(int[][] graph, int dir) {
        boolean[][] isChanged = new boolean[graph.length][graph.length];
        int n = graph.length;
        if (dir == 0) {
            for (int i = 0; i < graph.length; i++) {
                for (int j = graph[0].length - 2; j >= 0; j--) {
                    if (graph[i][j] == 0) {
                        continue;
                    }
                    while (j + 1 < n&& graph[i][j + 1] == 0) {
                        graph[i][j + 1] = graph[i][j];
                        graph[i][j] = 0;
                        j++;
                    }
                    if(j != n-1 && !isChanged[i][j+1] && graph[i][j] == graph[i][j+1]){
                        graph[i][j] = 0;
                        graph[i][j+1] *= 2;
                        isChanged[i][j+1] = true;
                    }

                }
            }
        }
        if(dir == 1){
            for (int i = 0; i < n; i++) {
                for (int j = n-2; j >= 0; j--) {
                    if(graph[j][i] == 0)
                        continue;
                    while (j + 1 < n && graph[j + 1][i] == 0) {
                        graph[j + 1][i] = graph[j][i];
                        graph[j][i] = 0;
                        j++;
                    }

                    if (j != n - 1 && !isChanged[j + 1][i] && graph[j][i] == graph[j + 1][i]) {
                        graph[j][i] = 0;
                        graph[j+1][i] *= 2;
                        isChanged[j+1][i] = true;
                    }
                }
            }
        }
        if (dir == 2) {
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    if(graph[i][j] == 0)
                        continue;
                    while (j - 1 >= 0 && graph[i][j - 1] == 0) {
                        graph[i][j-1] = graph[i][j];
                        graph[i][j] = 0;
                        j--;
                    }
                    if (j > 0 && !isChanged[i][j - 1] && graph[i][j] == graph[i][j - 1]) {
                        graph[i][j] = 0;
                        graph[i][j-1] *= 2;
                        isChanged[i][j-1] = true;
                    }
                }
            }
        }

        if (dir == 3) {
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < n; j++) {

                    if(graph[j][i] == 0)
                        continue;
                    while (j - 1 >= 0 && graph[j - 1][i] == 0) {
                        graph[j-1][i] = graph[j][i];
                        graph[j][i] = 0;
                        j--;
                    }
                    if (j > 0 && !isChanged[j - 1][i] && graph[j][i] == graph[j - 1][i]) {
                        graph[j][i]= 0;
                        graph[j-1][i] *= 2;
                        isChanged[j-1][i] = true;
                    }
                }
            }
        }
        return graph;
    }
}