[BOJ] 12100 2048 (Easy)

2048 게임을 직접 시뮬레이션 해보는 문제다.

기본적인 게임 규칙을 이해하고 짜는 것이 중요하다.

최대 5번 이동시켰을 때 남는 블록들 중 최대 값을 구하는 것이라

매 이동마다 상하좌우 4방향에 대해 재귀 호출로 게임판을 갱신시켜준다.

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <string>
#include <random>
#include <string.h> //gcc memset
using namespace std;
 
int _max(int a, int b) { return (a > b) ? a : b; }
 
int N = 0; //보드의 크기 (N x N)
vector<vector<int>> board; //보드
int answer = 0; //답이 되는 가장 큰 블록의 값
 
//재귀 호출로 블럭을 이동시킴.
//direction : 0=상,1=하,2=좌,3=우 moveCount : 현재 이동횟수
int solve(vector<vector<int>> _tempBoard, int direction, int moveCount)
{
    int maxValue = 0;
    int x = 0, y = 0, k = 0;
    //위쪽 이동
    if (direction == 0)
    {
        /*
        1) 체크 중인 방향의 반대 방향으로 0 ~ N-1 인덱스 범위내에서 순회.
        2) 최초 0이 아닌 블럭을 찾으면 해당 인덱스를 따로 저장 후, 다음 0이 아닌 블럭이 왔을 때 두 블럭의 값이 같은지 체크.
        3) 같으면 최초에 저장된 블럭에 값을 갱신하고 나중에 찾은 블럭은 0으로 갱신함.
        4) 3)에서 갱신 후 다음 0이 아닌 블럭을 찾으면 2)의 과정을 진행.
        5) 1) ~ 4) 과정이 모두 끝난 뒤 체크 중인 방향으로 빈 칸없이 쭉 밀어준다.
        */
        for (x = 0; x < N; ++x)
        {
            int add_y = -1;
            for (y = 0; y <= N - 1; ++y)
            {
                if (add_y == -1 && _tempBoard[y][x] != 0)
                    add_y = y;
                else if (add_y != -1 && _tempBoard[y][x] != 0)
                {
                    if (_tempBoard[add_y][x] == _tempBoard[y][x])
                    {
                        _tempBoard[add_y][x] += _tempBoard[y][x];
                        _tempBoard[y][x] = 0;
                        add_y = -1;
                    }
                    else
                        add_y = y;
                }
            }
 
            for (y = 1; y < N; ++y)
            {
                int tempY = y;
                while (tempY >= 1)
                {
                    if (_tempBoard[tempY - 1][x] == 0)
                    {
                        swap(_tempBoard[tempY - 1][x], _tempBoard[tempY][x]);
                        tempY--;
                    }
                    else
                        break;
                }
            }
        }
    }
    //아래쪽 이동
    else if (direction == 1)
    {
        for (x = 0; x < N; ++x)
        {
            int add_y = -1;
            for (y = N - 1; y >= 0; --y)
            {
                if (add_y == -1 && _tempBoard[y][x] != 0)
                    add_y = y;
                else if (add_y != -1 && _tempBoard[y][x] != 0)
                {
                    if (_tempBoard[add_y][x] == _tempBoard[y][x])
                    {
                        _tempBoard[add_y][x] += _tempBoard[y][x];
                        _tempBoard[y][x] = 0;
                        add_y = -1;
                    }
                    else
                        add_y = y;
                }
            }
 
            for (y = N - 2; y >= 0; --y)
            {
                int tempY = y;
                while (tempY <= N - 2)
                {
                    if (_tempBoard[tempY + 1][x] == 0)
                    {
                        swap(_tempBoard[tempY + 1][x], _tempBoard[tempY][x]);
                        tempY++;
                    }
                    else
                        break;
                }
            }
        }
    }
    //왼쪽 이동
    else if (direction == 2)
    {
        for (y = 0; y < N; ++y)
        {
            int add_x = -1;
            for (x = 0; x <= N - 1; ++x)
            {
                if (add_x == -1 && _tempBoard[y][x] != 0)
                    add_x = x;
                else if (add_x != -1 && _tempBoard[y][x] != 0)
                {
                    if (_tempBoard[y][add_x] == _tempBoard[y][x])
                    {
                        _tempBoard[y][add_x] += _tempBoard[y][x];
                        _tempBoard[y][x] = 0;
                        add_x = -1;
                    }
                    else
                        add_x = x;
                }
            }
 
            for (x = 1; x < N; ++x)
            {
                int tempX = x;
                while (tempX >= 1)
                {
                    if (_tempBoard[y][tempX - 1] == 0)
                    {
                        swap(_tempBoard[y][tempX - 1], _tempBoard[y][tempX]);
                        tempX--;
                    }
                    else
                        break;
                }
            }
        }
    }
    //오른쪽 이동
    else
    {
        for (y = 0; y < N; ++y)
        {
            int add_x = -1;
            for (x = N - 1; x >= 0; --x)
            {
                if (add_x == -1 && _tempBoard[y][x] != 0)
                    add_x = x;
                else if (add_x != -1 && _tempBoard[y][x] != 0)
                {
                    if (_tempBoard[y][add_x] == _tempBoard[y][x])
                    {
                        _tempBoard[y][add_x] += _tempBoard[y][x];
                        _tempBoard[y][x] = 0;
                        add_x = -1;
                    }
                    else
                        add_x = x;
                }
            }
 
            for (x = N - 2; x >= 0; --x)
            {
                int tempX = x;
                while (tempX <= N - 2)
                {
                    if (_tempBoard[y][tempX + 1] == 0)
                    {
                        swap(_tempBoard[y][tempX + 1], _tempBoard[y][tempX]);
                        tempX++;
                    }
                    else
                        break;
                }
            }
        }
    }
 
    //5번 이동했으면 최대값을 가지는 칸을 찾는다.
    if (moveCount == 5)
    {
        for (y = 0; y < N; ++y)
            for (x = 0; x < N; ++x)
                maxValue = _max(maxValue, _tempBoard[y][x]);
 
        return maxValue;
    }
    
    //이동횟수가 5회 미만일 경우 다음 4방향의 이동을 재귀 호출로 진행한다.
    for (k = 0; k < 4; ++k)
        maxValue = _max(solve(_tempBoard, k, moveCount + 1), maxValue);
 
    return maxValue;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N;
    board.resize(N);
    for (int k = 0; k < N; ++k)
        board[k].resize(N);
 
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x)
            cin >> board[y][x];
 
    for(int x = 0; x < 4; ++x)
        answer = _max(solve(board, x, 1), answer);
 
    cout << answer << "\n";
 
    return 0;
}