[BOJ 12100] 2048 (Easy) (Java) - 큐(Queue) 병합 시뮬레이션과 2차원 배열 원복

문제 정보

• 문제 링크: 백준 12100번 - 2048 (Easy)
• 난이도: Gold II
• 시간 / 메모리 제한: 1초 / 512 MB

핵심 조건 요약

• N × N(1 ≤ N ≤ 20) 보드에서 상·하·좌·우 네 방향 중 하나로 전체 블록을 이동시킵니다.
• 같은 값을 갖는 두 블록이 충돌하면 하나로 합쳐지지만, 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없습니다.
• 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구합니다.

---

접근 아이디어

최대 이동 횟수가 5번이고 매번 선택 가능한 방향이 4개이므로 전체 경우의 수는 4^5 = 1,024가지뿐입니다. 따라서 DFS 완전 탐색으로 모든 이동 조합을 시뮬레이션할 수 있습니다.

1. 한 번의 이동에서 연쇄 병합을 막는 큐(Queue) 로직

예를 들어 한 줄이 [2, 2, 4, 0]일 때 왼쪽으로 밀면 [4, 4, 0, 0]이 되어야지 [8, 0, 0, 0]이 되면 안 됩니다. 이를 깔끔하게 처리하기 위해 **큐(Queue)**와 **쓰기 포인터(index)**를 사용합니다.

1. 해당 행/열의 0이 아닌 블록을 미는 방향의 앞쪽부터 차례로 큐 q에 담고, 보드 칸은 0으로 초기화합니다.
2. index를 시작 끝점(0 또는 n - 1)에 두고 큐에서 블록 cur를 하나씩 꺼냅니다.
   • map[index] == 0: 현재 자리가 비어 있으므로 cur를 그대로 배치합니다. (index는 유지 → 다음 블록과 병합 가능성 열어둠)
   • map[index] == cur: 직전에 배치한 블록과 값이 같으므로 cur * 2로 병합한 뒤 index를 다음 칸으로 이동시켜 더 이상 연쇄 병합이 일어나지 않도록 잠급니다!
   • map[index] != cur: 값이 다르므로 index를 다음 칸으로 이동한 뒤 새 칸에 cur를 배치합니다.

2. 2차원 배열 깊은 복사 원복

DFS로 다음 깊이를 탐색하고 돌아올 때는 map이 이동 후 상태로 변형되어 있으므로, rotate() 진입 시점에 **행 단위로 .clone()해 둔 nextMap**으로 보드를 원상 복구해야 합니다.

---

Java 풀이 코드

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

import static java.util.Arrays.stream;

public class Main {

    static int n;
    static int[][] map;
    static int ans = 0;

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

        for (int i = 0; i < n; i++) {
            map[i] = stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

        rotate(0);
        System.out.println(ans);
    }

    private static void rotate(int count) {
        if (count == 5) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    ans = Math.max(ans, map[i][j]);
                }
            }
            return;
        }

        // 백트래킹 복구를 위해 현재 2차원 보드 상태 깊은 복사
        int[][] nextMap = new int[n][n];
        for (int k = 0; k < n; k++) {
            nextMap[k] = map[k].clone();
        }

        // 0: 좌, 1: 우, 2: 하, 3: 상
        for (int i = 0; i < 4; i++) {
            move(i);
            rotate(count + 1);
            for (int k = 0; k < n; k++) {
                map[k] = nextMap[k].clone();
            }
        }
    }

    static void move(int dir) {
        LinkedList<Integer> q = new LinkedList<>();

        if (dir == 0) { // 왼쪽으로 몰기
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j] != 0) q.add(map[i][j]);
                    map[i][j] = 0;
                }

                int index = 0;
                while (!q.isEmpty()) {
                    int cur = q.poll();
                    if (map[i][index] == 0) {
                        map[i][index] = cur;
                    } else if (map[i][index] == cur) {
                        map[i][index] = cur * 2;
                        index++;
                    } else {
                        index++;
                        map[i][index] = cur;
                    }
                }
            }
        } else if (dir == 1) { // 오른쪽으로 몰기
            for (int i = 0; i < n; i++) {
                for (int j = n - 1; j >= 0; j--) {
                    if (map[i][j] != 0) q.add(map[i][j]);
                    map[i][j] = 0;
                }

                int index = n - 1;
                while (!q.isEmpty()) {
                    int cur = q.poll();
                    if (map[i][index] == 0) {
                        map[i][index] = cur;
                    } else if (map[i][index] == cur) {
                        map[i][index] = cur * 2;
                        index--;
                    } else {
                        index--;
                        map[i][index] = cur;
                    }
                }
            }
        } else if (dir == 2) { // 아래쪽으로 몰기
            for (int i = 0; i < n; i++) {
                for (int j = n - 1; j >= 0; j--) {
                    if (map[j][i] != 0) q.add(map[j][i]);
                    map[j][i] = 0;
                }

                int index = n - 1;
                while (!q.isEmpty()) {
                    int cur = q.poll();
                    if (map[index][i] == 0) {
                        map[index][i] = cur;
                    } else if (map[index][i] == cur) {
                        map[index][i] = cur * 2;
                        index--;
                    } else {
                        index--;
                        map[index][i] = cur;
                    }
                }
            }
        } else if (dir == 3) { // 위쪽으로 몰기
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[j][i] != 0) q.add(map[j][i]);
                    map[j][i] = 0;
                }

                int index = 0;
                while (!q.isEmpty()) {
                    int cur = q.poll();
                    if (map[index][i] == 0) {
                        map[index][i] = cur;
                    } else if (map[index][i] == cur) {
                        map[index][i] = cur * 2;
                        index++;
                    } else {
                        index++;
                        map[index][i] = cur;
                    }
                }
            }
        }
    }
}

팁: 4방향 로직이 중복되는 것이 부담스럽다면, 보드를 시계 방향으로 90도 회전시키는 rotateBoard() 메서드와 한 방향(예: 왼쪽) 밀기 메서드 하나만 작성해 조합하는 방식으로 코드 길이를 절반 이하로 줄일 수도 있습니다.

---

채점 결과

---

복잡도 분석

• 시간 복잡도: O(4^5 × N^2) — 1,024 × 400 ≈ 4 × 10^5 연산 수준으로 매우 빠름
• 공간 복잡도: O(5 × N^2) — 재귀 깊이 5만큼의 보드 복제본 저장 공간