[백준] 12100번 - 2048 (Easy) (Gold 2)

문제 링크

백준 12100번 - 2048 (Easy) (Gold 2)

문제 설명

N x N 크기의 보드에서 2048 게임을 한다.
초기 보드의 크기와 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하시오.
원래의 2048 게임과 달리 이동할 때 추가되는 블록은 없다.

정답 코드 및 설명

가장 큰 블록의 값은 이동을 시행했을 때 감소할 수 없다.
따라서 5번 이동했을 때만 생각하면 되고, 총 경우의 수는 $4^5 = 1024$가지이다.
총 경우의 수가 매우 적으므로 모든 경우를 백트래킹으로 탐색해서 풀 수 있다.

이동을 구현하는 것이 코드의 가장 핵심적인 부분이다.
아래 코드에서는 두 개의 큐를 사용하여 이동을 구현했다.
첫번째 큐에는 0을 제외한 같은 행(또는 열)의 값을 순서대로 집어넣는다.
두번째 큐에는 이동 후 합쳐진 블록의 값을 순서대로 구해서 넣는다.
아래 코드의 51행~65행이 이를 구현하는 부분이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ12100 {
    final int MAX_DEPTH = 5;

    int size;
    int[][] initialBoard;
    ArrayList<Integer> maxNumber = new ArrayList<>();

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        size = Integer.parseInt(br.readLine());
        initialBoard = new int[size][size];
        StringTokenizer st;
        for (int i = 0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < size; j++) {
                initialBoard[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    int[][] move(int[][] initialBoard, Direction direction) {
        if (direction.equals(Direction.LEFT))
            return moveLeftRight(initialBoard, 1);
        if (direction.equals(Direction.RIGHT))
            return moveLeftRight(initialBoard, -1);
        if (direction.equals(Direction.UP))
            return moveUpDown(initialBoard, 1);
        if (direction.equals(Direction.DOWN))
            return moveUpDown(initialBoard, -1);
        return initialBoard;
    }

    int[][] moveLeftRight(int[][] initialBoard, int order) {
        int[][] currBoard = new int[size][size];
        int start = 0;
        if (order == -1) start = size - 1;
        for (int i = 0; i < size; i++) {
            Queue<Integer> row = new LinkedList<>();
            for (int j = 0; j < size; j++) {
                if (initialBoard[i][start + order * j] == 0) continue;
                row.add(initialBoard[i][start + order * j]);
            }
            Queue<Integer> newRow = new LinkedList<>();
            while (!row.isEmpty()) {
                int before = row.poll();
                if (row.isEmpty()) { // 행의 마지막 블록을 가져온 경우
                    newRow.add(before);
                    break;
                }
                int after = row.peek(); // 다음 블록이 있는 경우
                if (before == after) { // 블록이 합쳐지는 경우
                    newRow.add(before + after);
                    row.poll(); // 이미 합쳐진 블록 제거
                } else { // 블록이 합쳐지지 않는 경우
                    newRow.add(before);
                }
            }
            int curr = start;
            while (!newRow.isEmpty()) {
                currBoard[i][curr] = newRow.poll();
                curr += order;
            }
        }
        return currBoard;
    }

    int[][] moveUpDown(int[][] initialBoard, int order) {
        int[][] currBoard = new int[size][size];
        int start = 0;
        if (order == -1) start = size - 1;
        for (int j = 0; j < size; j++) {
            Queue<Integer> column = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                if (initialBoard[start + order * i][j] == 0) continue;
                column.add(initialBoard[start + order * i][j]);
            }
            Queue<Integer> newColumn = new LinkedList<>();
            while (!column.isEmpty()) {
                int before = column.poll();
                if (column.isEmpty()) {
                    newColumn.add(before);
                    break;
                }
                int after = column.peek();
                if (before == after) {
                    newColumn.add(before + after);
                    column.poll();
                } else {
                    newColumn.add(before);
                }
            }
            int curr = start;
            while (!newColumn.isEmpty()) {
                currBoard[curr][j] = newColumn.poll();
                curr += order;
            }
        }
        return currBoard;
    }

    void backtracking(int depth, int[][] currBoard) {
        if (depth == MAX_DEPTH) {
            maxNumber.add(maxNumber(currBoard));
            return;
        }
        for (Direction direction : Direction.values()) {
            int[][] newBoard = move(currBoard, direction);
            backtracking(depth + 1, newBoard);
        }
    }

    int maxNumber(int[][] board) {
        int max = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (max < board[i][j]) max = board[i][j];
            }
        }
        return max;
    }

    int answer() {
        int max = 0;
        for (Integer integer : maxNumber) {
            if (max < integer) max = integer;
        }
        return max;
    }

    void solution() throws IOException {
        input();
        backtracking(0, initialBoard);
        System.out.println(answer());
    }

    public static void main(String[] args) throws IOException {
        new BOJ12100().solution();
    }

    enum Direction {
        LEFT, RIGHT, UP, DOWN
    }
}