[백준 온라인 저지(BOJ)] 12094번 2048(Hard) 자바 풀이

BOJ 12094번 2048(Hard) 문제 자바(java) 풀이

• 랭크 : 플레티넘5
• 백준 온라인 저지(BOJ) 12094번 2048(Hard) 문제 자바 풀이
• 백준 12094번 2048(Hard)

문제정리

이는 2048 게임을 직접 해보는 것이 더 빠르게 이해할 수 있을 것 같습니다.
간단히 이야기 하자면 2의 배수로만 이루어진 타일들이 있는데
같은 숫자의 타일이 겹쳐지면 더해지는 게임이며 최종적으로 2048이라는 숫자를 가지는 타일을 만들면 끝나느 게임입니다.
2048게임 해보기

문제풀이

처음에는 arrayList를 이용하였다가 시간초과를 해결할 수 없었습니다.
하지만 배열을 이용하고, 가지치기를 잘 하여 시간 내에 통과할 수 있었습니다.
이 문제는 EASY 문제와 달리 이동이 없을 경우 가지치기만 해서는 통과할 수 없습니다.

가지치기

1. 이동시켜도 같은 경우
   중복순열로 모든 경우를 구하기에는 양이 꽤 많습니다. 그래서 가지치기를 해야합니다.
   한 번 이동후 다음에 다시 이동했는데 변화가 없을 경우에는 더 이상 이동하지 않도록 합니다.

2. 이동시 최댓값(branch에서의 최대값)
   이 경우는 이 2048(easy) 문제 에서는 해주지 않아도 충분히 통과할 수 있습니다.
   하지만 2048(hard) 문제의 경우에는 이 가지치기도 해주어야 통과할 수 있습니다.
   이게 무슨 뜻이냐면 5번 이동하는 경우의 수가 여러가지가 있을 수 있겠죠??
   어떤 방법으로 5번을 모두 이동했다고 합시다. 이때의 최대값이 512라면 이와 같거나 더 큰 최대값을 갖기 위해서는
   이 전(4번 이동했을 경우)의 최대값이 최소 256이어야 합니다. 그래야 다음 이동으로 숫자가 합쳐져서 512가 될 테니까요
   branch_max[5] = 512
   branch_max[4] = 256
   branch_max[3] = 128
   branch_max[2] = 64
   branch_max[1] = 32
   이런 식으로 만들어 줍니다.
   그래서 각 분기 마다 그 분기의 최소한 가져야 하는 타일인 branch_max[k] 보다 작으면 탐색하지 않는 것입니다.

• 주의 할 점
  한 가지의 경우의 수가 끝날 때마다 백업해두었던 초기 배열을 가져와 다시 그 경우의 수에 맞게 이동시킨다. 저는 5번 이동 후 그 상태에서 계속 해서 이동해버렸습니다...

• 최대 5번의 이동
  10번 이동 후의 최댓값을 구하는 것이 아니라 최대 10번 이동가능할때 최댓값입니다. 주의!!

오른쪽으로 이동 로직

왼쪽과 오른쪽으로 이동의 로직은 같기 때문에 오른쪽으로 이동할때를 기준으로 설명드리겠습니다.
0을 제외하고 생각하면 생각보다 쉽습니다.

1. 행을 기준으로 탐색을 시작합니다
2. 0을 제외한 숫자를 queue에 담습니다.
3. 오른쪽으로의 이동은 오른쪽 끝(n-1)부터 탐색해야 합니다.
4. 새로운 배열의 값이 0이면 즉, 쓰여진 값이 없다면 queue에서 뺸 값을 그대로 넣습니다.
   • 값이 Queue에서 빼낸 값과 같다면 값을 더해서 2배로 만들어 준다.(128이었으면 128을 더해서 256이 된다.) 그리고 인덱스를 왼쪽으로 이동시킨다.
   • 값이 0도 아니고 같지 않다면 다음 인덱스(왼쪽 인덱스)에 값을 넣어준다.

12094 2048(Hard) 자바 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Main {    
    static int n;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] arr = {0,1,2,3};
    static int[] branch_max;
    static int max = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        branch_max = new int[11];

        int[][] map = new int[n][n];
        for(int i=0; i<n; i++){
            String[] temp = br.readLine().split(" ");
            for(int j=0; j<n; j++)
                map[i][j] = Integer.parseInt(temp[j]);
        }

        // 초기 max값 설정
        // 이보다 작으면 skip하기 위해서
        max = getMax(map);
        backtracking(0, map);

        System.out.println(max);

        br.close();
    }   

    public static void backtracking(int k, int[][] map){
        // 현재의 최댓값 찾기
        // k번째 branch에서의 최대 가져야 하는 값보다 작으면 skip
        int mm = getMax(map);
        if(mm <= branch_max[k])
            return;

        if(k == 10){
            max = Math.max(max, mm);
            int b = max;
            while(k > 0){
                branch_max[k--] = b;
                b /= 2;
            }
            return;
        }
        else{
            for(int i=0; i<4; i++){
                int[][] after = new int[n][n];
                after = move(map, i);

                // 변화가 없는 경우 가지치기
                if(isSame(map, after))
                    continue;

                backtracking(k+1, after);
            }
        }
    }

    public static int[][] move(int[][] map, int cmd){
        int[][] after = deepCopy(map);
        switch(cmd){
            case 0:
                after = left(after);
                break;
            case 1:
                after = right(after);
                break;
            case 2:
                after = rotateClockwise(after);
                after = right(after);
                after = rotateCounterClockwise(after);
                break;
            case 3:
                after = rotateClockwise(after);
                after = left(after);
                after = rotateCounterClockwise(after);
        }
        return after;
    }

    public static int[][] left(int[][] map){
        Queue<Integer> q = new LinkedList<>();
        int[][] newMap = new int[n][n];

        // 왼쪽에서 부터 확인
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] != 0)
                    q.offer(map[i][j]);
            }
            int idx = 0;
            while(!q.isEmpty()){
                int value = q.poll();
                if(newMap[i][idx] == 0)
                    newMap[i][idx] = value;
                else if(newMap[i][idx] == value)
                    newMap[i][idx++] += value;
                else
                    newMap[i][++idx] = value;
            }
        }
        return newMap;
    }

    public static int[][] right(int[][] map){
        // 위에부터 확인
        // 오른쪽에서 부터 확인
        Queue<Integer> q = new LinkedList<>();
        int[][] newMap = new int[n][n];

        for(int i=0; i<n; i++){
            for(int j=n-1; j>=0; j--){
                if(map[i][j] != 0)
                    q.offer(map[i][j]);
            }
            int idx = n-1;
            while(!q.isEmpty()){
                int value = q.poll();
                if(newMap[i][idx] == 0)
                    newMap[i][idx] = value;
                else if(newMap[i][idx] == value)
                    newMap[i][idx--] += value;
                else
                    newMap[i][--idx] = value;
            }
        }
        return newMap;
    }

    // 배열 시계방향 회전
    public static int[][] rotateClockwise(int[][] map){
        int[][] reverse = new int[n][n];

        for(int i=0; i<n; i++){
            for(int j=n-1; j>=0; j--){
                reverse[i][n-j-1] = map[j][i];
            }
        }
        return reverse;
    }

    // 배열 반시계 방향 회전
    public static int[][] rotateCounterClockwise(int[][] map){
        int[][] reverse = new int[n][n];

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                reverse[i][j] = map[j][n-1-i];
            }
        }
        return reverse;
    }

    // 이차원 배열 깊은 복사
    public static int[][] deepCopy(int[][] src){
        int[][] dest = new int[n][n];
        for(int i=0; i<n; i++){
            System.arraycopy(src[i], 0, dest[i], 0, src[i].length);
        }

        return dest;
    }

    public static boolean isSame(int[][] map, int[][] after){
        int cnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] == after[i][j])
                    cnt++;
            }
        }

        if(cnt == n*n)
            return true;
        else
            return false;
    }

    public static int getMax(int[][] map){
        int max = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int temp = map[i][j];
                if(max < temp)
                    max = temp;
            }
        }
        return max;
    }
}