[BOJ 12100] 2048(Easy) (C++)

2048(Easy) (Gold 2)

문제

전체 문제 보기

12100번: 2048 (Easy)

접근법

가장 큰 블록의 값을 구하기 위해서 좌우상하로 최대 5번까지 이동할 수 있습니다. 총 \(4^5 =1,024\)개의 경우의 수가 나오기 때문에 모든 경우의 수를 완전탐색하여 문제를 해결할 수 있습니다. 모든 경우의 수를 완전탐색하기 위해서는 백트레킹을 활용할 수 있습니다. 백트레킹에서 다음과 같이 탐색을 진행하여 문제를 해결했습니다.

• 깊이가 5라면 현재 레벨에서 가장 큰수 탐색 후 반환
• 깊이가 5가 아니라면 아래의 탐색을 4회 반복
  • 모든 블럭을 위로 이동
  • 이동한 레벨을 백트레킹으로 재귀 탐색
  • 현재 레벨을 90도 회전

위 탐색에서 가장 구현이 까다로웠던 부분은 블록의 이동입니다. 문제에서 주어진 블록의 이동은 상하좌우 4방향 이동입니다. 처음에는 4방향 이동을 위한 함수를 4개로 구현했더니, 비슷한 함수가 4개나 되면서 중복된 부분이 많아지고 오류도 함께 많아 지며 디버깅이 어렵게 되었습니다. 그래서 레벨을 회전하는 기능을 만들어 블록들은 한 방향으로 이동하고 대신 레벨을 90도 회전하여 다른 방향으로 이동하는 효과를 구현하였습니다.

전체 구현

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
using Level = vector<vector<int>>;

class Board
{
private:
    Level level;
    void Press_up();
    void Merge_up();

public:
    void InputData(int N);
    void PrintAll() const;
    void Move();
    int GetMaxValue() const;
    void Rotate();
};
void Board::InputData(int N)
{
    level.resize(N);
    for (int i = 0; i < N; ++i)
    {
        level[i].resize(N);
        for (int j = 0; j < N; ++j)
        {
            scanf("%d ", &level[i][j]);
        }
    }
}
void Board::PrintAll() const
{
    int N = level.size();
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            printf("%4d ", level[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
void Board::Press_up()
{
    // 위로 이동
    int N = level.size();

    for (int i = 1; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            for (int pos = i; pos > 0 && level[pos - 1][j] == 0; --pos)
            {
                level[pos -1][j] = level[pos][j];
                level[pos][j] = 0;
            }
        }
    }
}

void Board::Merge_up()
{
    int N = level.size();
    for (int i = 1; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (level[i][j] == level[i - 1][j])
            {
                level[i - 1][j] += level[i][j];
                level[i][j] = 0;
            }
        }
    }
}

void Board::Move()
{
    Press_up();
    Merge_up();
    Press_up();
}
int Board::GetMaxValue() const
{
    int N = level.size();
    int retval{};
    for(int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            retval = max(retval, level[i][j]);
        }
    return retval;
}
void Board::Rotate()
{
    Level temp = level;
    int N = temp.size();
    for(int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            level[i][j] = temp[j][N - 1 - i];
        }
}
int Backtracking(Board& board, int depth)
{
    if (depth == 5)
        return board.GetMaxValue();
    int retval{};

    Board temp = board;
    for (int i = 0; i < 4; ++i)
    {
        board.Move();

        retval = max(retval, Backtracking(board, depth + 1));

        // 90도 회전
        temp.Rotate();
        board = temp;
    }
    retval = max(retval, board.GetMaxValue());
    return retval;
}

int main() {
    int N; //  N (1 ≤ N ≤ 20)
    scanf("%d ", &N);
    Board board;

    board.InputData(N);
    int answer = Backtracking(board, 0);

    printf("%d\n", answer);

    return 0;
}