[JAVA] 백준 12100번 : 2048(Easy)

https://www.acmicpc.net/problem/12100

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main_12100 {
    static int N, maxBlock = 0;
    //위 0 왼쪽 1 아래 2 오른쪽 3
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[][] board = new int[N][N];
        for (int i = 0; i < N; i++) {
            board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        dfs(board, 1, 1);
        System.out.println(maxBlock);
    }
    private static void dfs(int[][] board, int cnt, int max){
        if(cnt > 5){
            maxBlock = Math.max(maxBlock, max);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int[][] cBoard = new int[N][N];
            move(board, cBoard, i);
            int tmpMax = getMax(cBoard);

            dfs(cBoard, cnt + 1, tmpMax);
        }

    }

    private static void move(int[][] board, int[][] cBoard, int dir) {
        Queue<Integer> queue = new LinkedList<>();
        int idx, block;
        switch (dir) {
            case 0: //위로 이동
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        if(board[j][i] != 0)
                            queue.add(board[j][i]);
                    }
                    idx = 0;
                    while (!queue.isEmpty()) {
                        block = queue.poll();
                        if(cBoard[idx][i] == 0)
                            cBoard[idx][i] = block;
                        else if (cBoard[idx][i] == block) {
                            cBoard[idx++][i] *= 2;
                        } else {
                            cBoard[++idx][i] = block;
                        }
                    }
                }
                break;
            case 1: //왼쪽
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        if (board[i][j] != 0)
                            queue.add(board[i][j]);
                    }
                    idx = 0;
                    while (!queue.isEmpty()) {
                        block = queue.poll();
                        if(cBoard[i][idx] == 0)
                            cBoard[i][idx] = block;
                        else if (cBoard[i][idx] == block) {
                            cBoard[i][idx++] *= 2;
                        } else {
                            cBoard[i][++idx] = block;
                        }
                    }
                }
                break;
            case 2: //아래
                for (int i = 0; i < N; i++) {
                    for (int j = N - 1; j >= 0; j--) {
                        if(board[j][i] != 0)
                            queue.add(board[j][i]);
                    }
                    idx = N-1;
                    while (!queue.isEmpty()) {
                        block = queue.poll();
                        if(cBoard[idx][i] == 0)
                            cBoard[idx][i] = block;
                        else if (cBoard[idx][i] == block) {
                            cBoard[idx--][i] *= 2;
                        } else {
                            cBoard[--idx][i] = block;
                        }
                    }
                }
                break;
            case 3: // 오른쪽
                for (int i = 0; i < N; i++) {
                    for (int j = N - 1; j >= 0; j--) {
                        if(board[i][j] != 0) queue.add(board[i][j]);
                    }
                    idx = N-1;
                    while (!queue.isEmpty()) {
                        block = queue.poll();
                        if(cBoard[i][idx] == 0)
                            cBoard[i][idx] = block;
                        else if (cBoard[i][idx] == block) {
                            cBoard[i][idx--] *= 2;
                        } else {
                            cBoard[i][--idx] = block;
                        }
                    }
                }
                break;
        }
    }

    private static int getMax(int[][] board) {
        int tmp = 0;
        for(int[] b : board){
            tmp = Math.max(tmp, Arrays.stream(b).max().getAsInt());
        }
        return tmp;
    }
}

💡 DFS, 백트래킹

풀이

• 한번 이동시 끝까지 쭉 진행, 숫자가 합쳐지는 건 이동방향으로 제일 먼저 있는 블록을 우선으로 함
• 경우에 따라 배열의 값이 바뀌는 경우므로 DFS로 진행해줘야 함 + 변경 횟수가 최대 5회로 제한되어 있으므로 백트레킹
• 한 줄에 있어서, 한번에 쫙~~ 이동하므로 각 칸끼리 얼마나 떨어졌는지는 상관 없다. -> 큐에 0이 아닌 숫자들을 모두 넣어주고, 처음부터 poll하며 연속되는 같은 숫자가 있다면 걔네끼리 더해 줌
  • 이때, 한번 계산된 블록은 중복 계산되면 안되므로, cBlock[현재]가 0인지 아닌지 판별한다
    • 0이면 연속된 a+b중 a에 해당하는 숫자므로 그냥 할당
    • cBlock[현재] = queue.poll() 라면 연속된 숫자가 동일한 경우 -> 2배 해주고 idx 다음으로 넘어감
    • cBlock[현재] =/= queue.poll() 라면 연속된 숫자가 동일하지 않음 -> 다음 칸에 poll()값 배정
• 모든 숫자들을 이동해 복사한 뒤, 복사된 배열에서 최대값을 뽑아 다음 재귀함수의 인자로 넘겨준다
• cnt > 5인 경우, 인자 중 하나인 max값을 사용해 현재 최대값을 갱신해준 뒤 탈출