백준 12100번: 2048 (Easy)

백준 12100번: 2048 (Easy)

12100번: 2048 (Easy)

백준 문제 오랜만이다! 그동안 다른 것을 하느라 신경못썼는데 하루에 한문제씩이라도 다시 풀어야겠다.

오늘 푼 문제는 게임 시뮬레이션 문제다. Easy라고 적혀있지만 나에게 있어서 전혀 Easy하지 않은 문제였다.

어떤 게임을 기반으로 만들어진 문제인 것 같은데 난 이런류의 게임을 하지 않아서 머리속에 바로 그려지지는 않았다

그림과 함께 설명되어 있으니 읽으면서 문제를 그려냈다.

 

그럼 도대체 어떻게 기울여서 블록들을 합치는 것을 구현해야 할까?

이 부분을 고민을 많이했는데 정말 시뮬레이션 그대로 한쪽으로 기울였을 때

이동이 가능하면 한칸씩 이동하게 하는 것은 코드도 길어지고 그렇게 영리한 방법이 아니다.

여러 블로그를 탐색한 결과 다음과 같이 풀면된다.

 

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;


int boardSize;
int answer = 0;
int gameField[20][20];


void tiltGameBoard(int idx)
{
    queue<int> blockQueue;
    if (idx == 0)
    {
        // up
        for (int col = 0; col < boardSize; col++)
        {
            for (int row = 0; row < boardSize; row++)
            {
                if (gameField[row][col] != 0)
                {
                    blockQueue.push(gameField[row][col]);
                    gameField[row][col] = 0;
                }
            }
            int h = 0;
            while (!blockQueue.empty())
            {
                int block = blockQueue.front();
                blockQueue.pop();
                if (gameField[h][col] == 0)
                {
                    gameField[h][col] = block;
                }
                else if (gameField[h][col] == block)
                {
                    gameField[h][col] *= 2;
                    h += 1;
                }
                else if (gameField[h][col] != block)
                {
                    h += 1;
                    gameField[h][col] = block;
                }
            }
        }
    }
    else if (idx == 1)
    {
        // left
        for (int row = 0; row < boardSize; row++)
        {
            for (int col = 0; col < boardSize; col++)
            {
                if (gameField[row][col] != 0)
                {
                    blockQueue.push(gameField[row][col]);
                    gameField[row][col] = 0;
                }
            }
            int w = 0;
            while (!blockQueue.empty())
            {
                int block = blockQueue.front();
                blockQueue.pop();
                if (gameField[row][w] == 0)
                {
                    gameField[row][w] = block;
                }
                else if (gameField[row][w] == block)
                {
                    gameField[row][w] *= 2;
                    w += 1;
                }
                else if (gameField[row][w] != block)
                {
                    w += 1;
                    gameField[row][w] = block;
                }
            }
        }
    }
    else if (idx == 2)
    {
        // down
        for (int col = 0; col < boardSize; col++)
        {
            for (int row = boardSize - 1; row >= 0; row--)
            {
                if (gameField[row][col] != 0)
                {
                    blockQueue.push(gameField[row][col]);
                    gameField[row][col] = 0;
                }
            }
            int h = boardSize - 1;
            while (!blockQueue.empty())
            {
                int block = blockQueue.front();
                blockQueue.pop();
                if (gameField[h][col] == 0)
                {
                    gameField[h][col] = block;
                }
                else if (gameField[h][col] == block)
                {
                    gameField[h][col] *= 2;
                    h -= 1;
                }
                else if (gameField[h][col] != block)
                {
                    h -= 1;
                    gameField[h][col] = block;
                }
            }
        }
    }
    else if (idx == 3)
    {
        // right
        for (int row = 0; row < boardSize; row++)
        {
            for (int col = boardSize - 1; col >= 0; col--)
            {
                if (gameField[row][col] != 0)
                {
                    blockQueue.push(gameField[row][col]);
                    gameField[row][col] = 0;
                }
            }
            int w = boardSize - 1;
            while (!blockQueue.empty())
            {
                int block = blockQueue.front();
                blockQueue.pop();
                if (gameField[row][w] == 0)
                {
                    gameField[row][w] = block;
                }
                else if (gameField[row][w] == block)
                {
                    gameField[row][w] *= 2;
                    w -= 1;
                }
                else if (gameField[row][w] != block)
                {
                    w -= 1;
                    gameField[row][w] = block;
                }
            }
        }
    }
}


void dfs(int depth)
{
    int copyBoard[20][20];
    // 최대 깊이는 5입니다.
    if (depth == 5)
    {
        for(int i = 0; i < boardSize; i++)
            for(int j = 0; j < boardSize; j++)
                answer = max(answer, gameField[i][j]);
        return;
    }
    for (int row = 0; row < boardSize; row++)
        for (int col = 0; col < boardSize; col++)
            copyBoard[row][col] = gameField[row][col];
    for (int dir = 0; dir < 4; dir++)
    {
        tiltGameBoard(dir);
        dfs(depth + 1);
        for (int row = 0; row < boardSize; row++)
            for (int col = 0; col < boardSize; col++)
                gameField[row][col] = copyBoard[row][col];
        
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> boardSize;
    for (int row = 0; row < boardSize; row++)
    {
        for (int col = 0; col < boardSize; col++)
        {
            cin >> gameField[row][col];
        }
    }
    dfs(0);
    cout << answer;
    return 0;
}