[백준 12094] 2048 (hard) - JAVA

WTS·2026년 3월 25일
구현리팩토링백준백트래킹시뮬레이션코딩테스트코딩테스트스터디

코딩 테스트

목록 보기
37/81

문제 링크 : https://www.acmicpc.net/problem/12094

코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!

문제 정의

  • 보드의 크기 N이 주어지고 다음 줄부터 N∗N의 입력이 주어짐
  • 상/하/좌/우 이동 가능, 같은 숫자는 한 번만 병합 가능
  • 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐짐
  • 최대 10번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력

이전 2048 (Easy) 문제와 동일하지만
이동 횟수가 5 -> 10으로 변경되었습니다.

시간 복잡도

사실 이동 횟수가 5회에서 10회로 증가한게 큰 차이가 있겠냐 싶겠지만
연산 횟수를 보면 그렇지 않습니다.

입력으로 주어지는 NN은 최대 2020
따라서 보드의 최대 넓이는 400400

이동 방향은 4방향,
5번 이동 가능하므로 경우의 수는 총 410=1,048,5764^{10}=1,048,576가지 입니다.

시간 복잡도는
O(N2∗410)O(N^2∗4^{10}) 이며
최대 연산 수는 419,430,400∗a419,430,400 * a회 입니다.

1억번의 연산을 1초로 환산한다면
기존의 로직을 사용하게 되면
TLE가 발생하게 됩니다.

그래서
이번 문제에서는
단순히 브루트포스를 수행하는 것이 아닌
pruning 기법을 사용한 백트래킹을 구현해야 합니다.

접근 방법

그렇다면 어떻게 접근해야할까?

2048 (Easy) 문제에서 구현했던
브루트포스 로직을 활용해 가지치기 로직을 활용한 백트래킹으로
코드를 리팩토링하면 되지 않을까? 라고 생각해서 시작했습니다.

기존의 코드

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

public class Main {
    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        int[][] board = new int[N][N];

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

        bf(0, board);
        System.out.println(max);
    }

    static void bf(int n, int[][] board) {
        if (n == 5) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    max = Math.max(max, board[i][j]);
                }
            }
            return;
        }

        bf(n + 1, up(copyBoard(board)));
        bf(n + 1, down(copyBoard(board)));
        bf(n + 1, left(copyBoard(board)));
        bf(n + 1, right(copyBoard(board)));
    }

    static int[][] copyBoard(int[][] board) {
        int[][] copyBoard = new int[N][N];
        for (int i = 0; i < N; i++){
            copyBoard[i] = Arrays.copyOf(board[i], N);
        }
        return copyBoard;
    }

    static int[][] up (int[][] board) {
        for (int j = 0; j < N; j++) {
            int pointer = 0;
            for (int i = 1; i < N; i++) {
                if (board[i][j] == 0) continue;

                int now = board[i][j];
                board[i][j] = 0;

                if (board[pointer][j] == 0) {
                    board[pointer][j] = now;
                }
                else {
                    if (board[pointer][j] == now) {
                        board[pointer][j] *= 2;
                        pointer++;
                    }
                    else {
                        pointer++;
                        board[pointer][j] = now;
                    }
                }
            }
        }
        return board;
    }

    static int[][] down (int[][] board) {
        for (int j = 0; j < N; j++) {
            int pointer = N-1;
            for (int i = N-2; i >= 0; i--) {
                if (board[i][j] == 0) continue;

                int now = board[i][j];
                board[i][j] = 0;

                if (board[pointer][j] == 0) {
                    board[pointer][j] = now;
                }
                else {
                    if (board[pointer][j] == now) {
                        board[pointer][j] *= 2;
                        pointer--;
                    }
                    else {
                        pointer--;
                        board[pointer][j] = now;
                    }
                }
            }
        }
        return board;
    }

    static int[][] left (int[][] board) {
        for (int i = 0; i < N; i++) {
            int pointer = 0;
            for (int j = 1; j < N; j++) {
                if (board[i][j] == 0) continue;

                int now = board[i][j];
                board[i][j] = 0;

                if (board[i][pointer] == 0) {
                    board[i][pointer] = now;
                }
                else {
                    if (board[i][pointer] == now) {
                        board[i][pointer] *= 2;
                        pointer++;
                    }
                    else {
                        pointer++;
                        board[i][pointer] = now;
                    }
                }
            }
        }
        return board;
    }

    static int[][] right (int[][] board) {
        for (int i = 0; i < N; i++) {
            int pointer = N-1;
            for (int j = N-2; j >= 0; j--) {
                if (board[i][j] == 0) continue;

                int now = board[i][j];
                board[i][j] = 0;

                if (board[i][pointer] == 0) {
                    board[i][pointer] = now;
                }
                else {
                    if (board[i][pointer] == now) {
                        board[i][pointer] *= 2;
                        pointer--;
                    }
                    else {
                        pointer--;
                        board[i][pointer] = now;
                    }
                }
            }
        }
        return board;
    }
}

브루트포스로 구현된 2048 (Easy) 코드입니다.
우선 어떻게 리팩토링할 수 있을까요?

가지치기 방법

제가 고민한 가지치기 방법은 다음과 같습니다.

  1. 이동 로직을 수행했는데 이동이 없는 경우 가지치기를 하자
  2. 최댓값 가능성을 계산해 가지치기를 하자

1. 이동 로직을 수행했는데 이동이 없는 경우 가지치기

각각의 상/하/좌/우 로직을 수행했을 때
말 그대로 숫자들이 위쪽 벽면에 붙어있거나 이미 해당 방향으로 정렬된 경우
이동 로직을 수행했음에도 변화가 없는 경우가 존재하게 됩니다.

이런 경우 이동 횟수만 감소되고
이동이 없게 되므로 최댓값 갱신 가능성이 없기 때문에 가지치기를 합니다.

그래서 어떻게?

간단합니다.

보드 이동 로직에
이동했는지 판단하는 변수를 넣고
한 번이라도 움직였다면 true를 주는 것입니다.

완성된 이동 로직이라 조금 다르지만
표시된 부분을 봐주시면

moved라는 boolean 변수를 선언하고
내부에서 한 번이라도 이동이 있다면 moved를 true로 처리합니다.

또한 상/하/좌/우 외부의 메서드에서는
다음과 같이 moved에 따라 이동된 보드 또는 null이 반환되는데
이동 되지 않아 null이 반환된 방향의 경우는
제외한 후에 다음 재귀를 수행하는 것을 볼 수 있습니다.

2. 최댓값 가능성을 계산해 가지치기

코드를 보면 내부에서 2배로 합쳐질 때 최댓값 갱신 로직을 수행하도록 구현했습니다.
이동만 한다고 최댓값이 갱신되지는 않으니
합쳐지는 순간 최댓값을 계속해서 갱신해주는 로직을 수행합니다.

이렇게 하면 매 메서드마다 갱신 로직에 의한 연산 횟수가 증가하겠지만
가지치기를 조금 더 컴펙트하게 구현하기 위해서 적용했습니다.

그래서 이렇게 하면 뭐가 좋은데?

if (current.max << (10 - n) <= max) return;

이 연산이 핵심입니다.

만약 현재까지 전역에 존재하는 max가 2048이라고 하고
현재 재귀에서의 current.max는 4, n은 3이라고 가정해보겠습니다.
그렇다면 남은 이동 횟수는 7
해당 보드에서 모두 합쳐진다고 가정했을 때 최댓값은
4∗27=5124 * 2^7 = 512로 최댓값이 절대로 될 수 없다는 것을 역산해서 알 수 있습니다.

이렇게 최댓값이 될 수 없는 케이스는 가지치기를 통해
최적화를 진행하였습니다.

BoardState 객체 사용

class BoardState {
    int[][] board;
    int max;

    public BoardState(int[][] board, int max) {
        this.board = board;
        this.max = max;
    }
}

다음 보드를 넘겨줄 때
기존 로직은 int[][]를 사용했지만
각 보드의 최댓값을 같이 저장해주기 위해서
BoardState라는 객체를 사용했습니다.

이렇게 하면 현재 보드에 대한 최댓값 조회가 용이할 뿐만 아니라
좀 더 직관적으로 용도를 파악할 수 있습니다.

코드

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


class BoardState {
    int[][] board;
    int max;

    public BoardState(int[][] board, int max) {
        this.board = board;
        this.max = max;
    }
}

public class Main {
    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int max = 0;


    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        int[][] board = new int[N][N];

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

        bt(0, new BoardState(board, max));
        System.out.println(max);
    }

    static void bt(int n, BoardState current) {
        if (n == 10) {
            max = Math.max(max, current.max);
            return;
        }

        if (current.max << (10 - n) <= max) return;

        BoardState[] nextBoard = new BoardState[4];
        nextBoard[0] = up(current);
        nextBoard[1] = down(current);
        nextBoard[2] = left(current);
        nextBoard[3] = right(current);

        for (BoardState board : nextBoard) {
            if (board != null) bt(n + 1, board);
        }
    }

    static BoardState copyBoard(BoardState current) {
        int[][] copyBoard = new int[N][N];
        for (int i = 0; i < N; i++){
            copyBoard[i] = Arrays.copyOf(current.board[i], N);
        }
        return new BoardState(copyBoard, current.max);
    }

    static BoardState up (BoardState current) {
        BoardState copy = copyBoard(current);
        boolean moved = false;

        for (int j = 0; j < N; j++) {
            int pointer = 0;
            for (int i = 1; i < N; i++) {
                if (copy.board[i][j] == 0) continue;

                int now = copy.board[i][j];
                copy.board[i][j] = 0;

                if (copy.board[pointer][j] == 0) {
                    copy.board[pointer][j] = now;
                    if (pointer != i) moved = true;
                }
                else {
                    if (copy.board[pointer][j] == now) {
                        copy.board[pointer][j] *= 2;
                        copy.max = Math.max(copy.max, now * 2);
                        moved = true;
                        pointer++;
                    }
                    else {
                        pointer++;
                        if (pointer != i) moved = true;
                        copy.board[pointer][j] = now;
                    }
                }
            }
        }
        return moved ? copy : null;
    }

    static BoardState down (BoardState current) {
        BoardState copy = copyBoard(current);
        boolean moved = false;

        for (int j = 0; j < N; j++) {
            int pointer = N-1;
            for (int i = N-2; i >= 0; i--) {
                if (copy.board[i][j] == 0) continue;

                int now = copy.board[i][j];
                copy.board[i][j] = 0;

                if (copy.board[pointer][j] == 0) {
                    copy.board[pointer][j] = now;
                    if (pointer != i) moved = true;
                }
                else {
                    if (copy.board[pointer][j] == now) {
                        copy.board[pointer][j] *= 2;
                        copy.max = Math.max(copy.max, now * 2);
                        moved = true;
                        pointer--;
                    }
                    else {
                        pointer--;
                        copy.board[pointer][j] = now;
                        if (pointer != i) moved = true;
                    }
                }
            }
        }
        return moved ? copy : null;
    }

    static BoardState left (BoardState current) {
        BoardState copy = copyBoard(current);
        boolean moved = false;

        for (int i = 0; i < N; i++) {
            int pointer = 0;
            for (int j = 1; j < N; j++) {
                if (copy.board[i][j] == 0) continue;

                int now = copy.board[i][j];
                copy.board[i][j] = 0;

                if (copy.board[i][pointer] == 0) {
                    copy.board[i][pointer] = now;
                    if (pointer != j) moved = true;
                }
                else {
                    if (copy.board[i][pointer] == now) {
                        copy.board[i][pointer] *= 2;
                        copy.max = Math.max(copy.max, now * 2);
                        moved = true;
                        pointer++;
                    }
                    else {
                        pointer++;
                        copy.board[i][pointer] = now;
                        if (pointer != j) moved = true;
                    }
                }
            }
        }
        return moved ? copy : null;
    }

    static BoardState right (BoardState current) {
        BoardState copy = copyBoard(current);
        boolean moved = false;

        for (int i = 0; i < N; i++) {
            int pointer = N-1;
            for (int j = N-2; j >= 0; j--) {
                if (copy.board[i][j] == 0) continue;

                int now = copy.board[i][j];
                copy.board[i][j] = 0;

                if (copy.board[i][pointer] == 0) {
                    copy.board[i][pointer] = now;
                    if (pointer != j) moved = true;
                }
                else {
                    if (copy.board[i][pointer] == now) {
                        copy.board[i][pointer] *= 2;
                        copy.max = Math.max(copy.max, now * 2);
                        moved = true;
                        pointer--;
                    }
                    else {
                        pointer--;
                        copy.board[i][pointer] = now;
                        if (pointer != j) moved = true;
                    }
                }
            }
        }
        return moved ? copy : null;
    }
}
profile
WTS
while True: study()
이전 포스트

[백준 12100] 2048 (Easy) - JAVA

다음 포스트

[백준 2239] 스도쿠 - JAVA

0개의 댓글