[C++] 백준 12100 2048 (Easy)

#include <iostream>
#include <algorithm>
#include <vector>
 
int N = 0;
long long ans = 0;
 
long long GetMax(std::vector<std::vector<long long>> board)
{
    long long temp = 0;
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            temp = std::max(temp, board[i][j]);
        }
    }
 
    return temp;
}
 
std::vector<std::vector<long long>> Right(std::vector<std::vector<long long>> board)
{
    std::vector<std::vector<bool>> check(N, std::vector<bool>(N, false));
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = N - 2; j >= 0; --j)
        {
            if (!board[i][j])
                continue;
 
            for (int k = j + 1; k < N; ++k)
            {
                if (board[i][k] == board[i][k - 1] && !check[i][k])
                {
                    board[i][k] *= 2;
                    board[i][k - 1] = 0;
                    check[i][k] = true;
 
                    break;
                }
 
                else if (!board[i][k])
                {
                    board[i][k] = board[i][k - 1];
                    board[i][k - 1] = 0;
                }
 
                else
                    break;
            }
        }
    }
 
    return board;
}
 
std::vector<std::vector<long long>> Left(std::vector<std::vector<long long>> board)
{
    std::vector<std::vector<bool>> check(N, std::vector<bool>(N, false));
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 1; j < N; ++j)
        {
            if (!board[i][j])
                continue;
 
            for (int k = j - 1; k >= 0; --k)
            {
                if (board[i][k] == board[i][k + 1] && !check[i][k])
                {
                    board[i][k] *= 2;
                    board[i][k + 1] = 0;
                    check[i][k] = true;
                    break;
                }
 
                else if (!board[i][k])
                {
                    board[i][k] = board[i][k + 1];
                    board[i][k + 1] = 0;
                }
 
                else
                    break;
            }
        }
    }
 
    return board;
}
 
std::vector<std::vector<long long>> Down(std::vector<std::vector<long long>> board)
{
    std::vector<std::vector<bool>> check(N, std::vector<bool>(N, false));
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = N - 2; j >= 0; --j)
        {
            if (!board[j][i])
                continue;
 
            for (int k = j + 1; k < N; ++k)
            {
                if (board[k][i] == board[k - 1][i] && !check[k][i])
                {
                    board[k][i] *= 2;
                    board[k - 1][i] = 0;
                    check[k][i] = true;
                    break;
                }
 
                else if (!board[k][i])
                {
                    board[k][i] = board[k - 1][i];
                    board[k - 1][i] = 0;
                }
 
                else
                    break;
            }
        }
    }
 
    return board;
}
 
std::vector<std::vector<long long>> Up(std::vector<std::vector<long long>> board)
{
    std::vector<std::vector<bool>> check(N, std::vector<bool>(N, false));
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 1; j < N; ++j)
        {
            if (!board[j][i])
                continue;
 
            for (int k = j - 1; k >= 0; --k)
            {
                if (board[k][i] == board[k + 1][i] && !check[k][i])
                {
                    board[k][i] *= 2;
                    board[k + 1][i] = 0;
                    check[k][i] = true;
                    break;
                }
 
                else if (!board[k][i])
                {
                    board[k][i] = board[k + 1][i];
                    board[k + 1][i] = 0;
                }
 
                else
                    break;
            }
        }
    }
 
    return board;
}
 
void DFS(int count, std::vector<std::vector<long long>> board)
{
    ans = std::max(ans, GetMax(board));
 
    if (count == 5)
        return;
 
    DFS(count + 1, Right(board));
    DFS(count + 1, Left(board));
    DFS(count + 1, Up(board));
    DFS(count + 1, Down(board));
}
 
int main()
{
    std::cin >> N;
    std::vector<std::vector<long long>> board(N, std::vector<long long>(N));
 
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            std::cin >> board[i][j];
        }
    }
 
    DFS(0, board);
    std::cout << ans;
 
    return 0;
}

DFS로 모든 방향으로 5번 회전시킵니다.

회전 시킬 때 숫자가 없을 경우 다음으로,

번호가 있다면 옆으로 미는데 같은 숫자라면 합칩니다.

(이 때, 합쳐지면 다시 합쳐지면 안되기 때문에 check로 다음에 합쳐지지 않게 만듭니다.)

5번 전부 옮겼다면 바로 Max체크를 합니다.