백준 - 12100 2048 (Easy)

코드

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

public class RotateArray {

    static int answer = -1;

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

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

        System.out.println(answer);

    }

    public static void dfs(int[][] arr, int count) {

        if (count == 5) {
            findMax(arr);
            return;
        }

        for (int i = 0; i <= 3; i++) {
            int[][] copyArray = copyArray(arr);
            int[][] ints = pushDown(copyArray);
            dfs(ints, count + 1);
            rotateAngle(arr);
        }
    }

    public static int[][] copyArray(int[][] arr) {
        int len = arr.length;
        int[][] copyArray = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                copyArray[i][j] = arr[i][j];
            }
        }
        return copyArray;
    }

    public static void rotateAngle(int[][] arr) {

        int len = arr.length;

        for (int i = 0; i < len / 2; i++) {
            for (int j = 0; j < len; j++) {
                int temp = arr[i][j];
                arr[i][j] = arr[len - i - 1][j];
                arr[len - i - 1][j] = temp;
            }

        }

        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                int temp = arr[i][j];
                arr[i][j] = arr[j][i];
                arr[j][i] = temp;
            }
        }

    }

    public static int[][] pushDown(int[][] arr) {
        Stack<Integer> stack = new Stack<>();

        int len = arr.length;
        int[][] newArray = new int[len][len];
        for (int i = 0; i < len; i++) {
            boolean isNew = true;
            for (int j = len - 1; j >= 0; j--) {
                int current = arr[j][i];

                if (current == 0)
                    continue;

                if (stack.empty() || stack.peek() != current) {
                    stack.push(current);
                    isNew = true;
                    continue;
                }
                //같은 값이지만 한번도 사용한 적 없는 값
                if (isNew) {
                    Integer pop = stack.pop();
                    stack.push(current + pop);
                    isNew = false; //사용함 표시
                    continue;
                }

                isNew = true;
                stack.push(current);
            }

            int count = len - stack.size();
            while (!stack.empty()) {
                newArray[count++][i] = stack.pop();
            }
        }
        return newArray;
    }

    public static void findMax(int[][] arr) {

        for (int[] ints : arr) {
            for (int j = 0; j < arr.length; j++) {
                answer = Math.max(ints[j], answer);
            }
        }

    }
}

해설

🧐코드에 대하여 설명하자면
1. dfs를 통해 깊이가 5까지 돌릴 것이다.
2. dfs에서는 pushdown함수를 통해 규칙대로 모든 숫자를 아래로 내려준다. 이 때 같은 값은 합쳐줘야 하는데 중요한 점은 한번 합친 값은 다시 합치면 안된다. (이것 때문에 거의 2시간을 잡아먹은 것 같다.) 더 이쁘게 풀 수 있겠지만 여기서는 flag를 선언하여 이미 사용한 값인지 체크하였다.
3. 4방향에 대해서 모두 체크를 해야하기 때문에 회전이 필수 인데 여기서는 한방향으로만 돌려서 4방향에 대하여 체크하도록 하였다. rotate함수를 통해 90도 씩 돌려준다.
4. 만약 깊이가 5에 도달한다면 최대 값을 구하여 answer에 저장해준다.

배열을 복사하는 과정도 많고 for문도 이중으로 돌리고 있어서 시간복잡도가 걱정될 수 있지만 깊이가 5인 dfs라서 가능한 풀이였다.

예전에 풀려고 시도했다가 근처도 못가고 실패했던 문제였는데 생각이 나서 다시 풀게 되었다. 생각보다도 더 어려웠던 문제이다. 나중에 다른 분들 풀이를 보니 아이디어 자체는 맞았는데 구현에서 꽤나 시간을 많이 잡아 먹었다.😭😭 특히 테스트케이스가 1개 밖에 없어서 디버깅도 쉽지 않은 문제이다.
만약 테스트가 잘 통과가 안된다면 아래를 확인해보자
1. rotate가 잘 되었는가?
2. push(한쪽으로 밀어넣기)가 잘 되었는가?
3. push할 경우 이미 한번 합친 값을 또 합치고 있지는 않은가?(이거 꼭 확인해 보는게 좋을 것 같습니다.)

출처 : 백준 - 2048 (Easy)