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

문제 링크

문제 풀이

예전에 유행했던 스마트폰 게임 2048에서 따온 문제이다. 문제로 만들면서 실제 게임과 달라진 조건이 존재하는데, 이동을 한 번 하여도 블록이 추가되지 않는다는 것이다.

 

처음에는 위, 아래, 오른쪽, 왼쪽으로 맵(Map)에 있는 블록을 이동시키고 합치는 함수를 각각 구현하려 했으나 더 좋은 방법이 떠올라 다른 방법을 이용하였다. 한 방향으로 블록(Block)을 이동시키는 함수를 구현하고, 맵(Map)을 90도 회전시키는 함수를 구현하여 두 함수를 적절히 함께 사용해 4방향으로 이동하는 경우의 수를 따지는 방법이었다. 아래의 코드는 작성한 풀이 방법대로 구현한 코드이다.

코드

#include <iostream>

using namespace std;

int N;
int result = 2;

int originalMap[30][30];
int copiedMap[30][30];

int movedMapLine[30];

void rotateCopiedMap()
{
    int temp[30][30];
    for (int yp = 0; yp < N; yp++)
        for (int xp = 0; xp < N; xp++)
            temp[yp][xp] = copiedMap[yp][xp];
    for (int yp = 0; yp < N; yp++)
        for (int xp = 0; xp < N; xp++)
            copiedMap[N - 1 - xp][yp] = temp[yp][xp];
}

void moveBlocks(int direction)
{
    for (int i = 0; i < direction; i++)
        rotateCopiedMap();

    for (int yp = 0; yp < N; yp++)
    {
        int idx = 0;
        for (int xp = 0; xp < N; xp++)
            movedMapLine[xp] = 0;
        for (int xp = 0; xp < N; xp++)
        {
            if (copiedMap[yp][xp] == 0)
                continue;
            if (movedMapLine[idx] == 0)
                movedMapLine[idx] = copiedMap[yp][xp];
            else if (movedMapLine[idx] == copiedMap[yp][xp])
                movedMapLine[idx++] *= 2;
            else
                movedMapLine[++idx] = copiedMap[yp][xp];
        }
        for (int xp = 0; xp < N; xp++)
            copiedMap[yp][xp] = movedMapLine[xp];
    }

    for (int i = 4 - direction; i < 4; i++)
        rotateCopiedMap();
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int yp = 0; yp < N; yp++)
        for (int xp = 0; xp < N; xp++)
            cin >> originalMap[yp][xp];

    for (int way = 0; way < 1024; way++)
    {
        for (int yp = 0; yp < N; yp++)
            for (int xp = 0; xp < N; xp++)
                copiedMap[yp][xp] = originalMap[yp][xp];

        int brute = way;
        for (int i = 0; i < 5; i++)
        {
            int dir = brute % 4;
            brute /= 4;
            moveBlocks(dir);
        }

        for (int yp = 0; yp < N; yp++)
            for (int xp = 0; xp < N; xp++)
                result = max(result, copiedMap[yp][xp]);
    }

    cout << result << '\n';

    return 0;
}