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

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>	<그림 2>	<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>	<그림 5>	<그림 6>	<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>	<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>	<그림 15>

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

풀이

dfs로 완전탐색을 구현해서 풀었다. 

완전탐색을 진행할때 보드의 정보를 적절히 복사해주는게 중요하다.

전체 블록은 상하좌우로 이동가능하기 때문에 4가지 경우에 대한 함수를 따로 작성했다.

하지만 로직은 다 똑같고 반복문의 초기값 정도만 다르기 때문에 블록이 위로 이동하는 경우에 대해서만 설명하겠다.

 

전체 블록을 위로 이동시킬 경우

블록이 위로 이동하는 경우에는 보드의 열을 순서대로 확인해야 한다.

해당 열에 블록이 있으면 숫자들을 큐에 저장하고 해당 위치의 보드 정보는 0으로 변경한다.

그리고 큐에 저장되어 있는 숫자들을 하나씩 확인하며 게임을 진행한다.

1) 블록을 놓으려는 위치가 비어있다면 해당 위치로 현재 블록을 옮긴다.

2) 블록을 놓으려는 위치에 같은 숫자의 블록이 있다면 해당 숫자를 2배 증가시킨다.

3) 블록을 놓으려는 위치에 다른 숫자의 블록이 있다면 그 아래에 블록을 놓는다. 

나머지 아래, 왼쪽, 위쪽으로 이동할 경우에는 변수 초기값만 좀 다르다.

 

이를 코드로 구현하면 다음과 같다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAX 20
using namespace std;
int N, answer = 0;
int MAP[MAX][MAX];
// 블록의 숫자들을 저장할 큐
queue<int> num;
// 배열 복사
void copy(int arr[MAX][MAX], int arr2[MAX][MAX])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            arr2[i][j] = arr[i][j];
        }
    }
}
// 전체 블록 위로 이동
void up()
{
    for (int j = 0; j < N; j++)
    {
        // 블록을 놓을 위치
        int idx = 0;
        for (int i = 0; i < N; i++)
        {
            // 블록 발견하면 큐에 블록 숫자 추가
            if (MAP[i][j] != 0)
            {
                num.push(MAP[i][j]);
                // 해당 위치의 숫자는 0으로 변경
                MAP[i][j] = 0;
            }
        }
        while (!num.empty())
        {
            int current = num.front();
            num.pop();
            // 블록 놓으려는 곳이 비어있다면
            if (MAP[idx][j] == 0)
            {
                // 블록 위로 이동
                MAP[idx][j] = current;
            }
            // 블록 놓으려는 곳에 같은 숫자의 블록이 있다면
            else if (MAP[idx][j] == current)
            {
                // 해당 블록 숫자 2배 증가시키고 인덱스 증가
                MAP[idx++][j] *= 2;
            }
            // 블록 놓으려는 곳에 다른 숫자의 블록이 있다면
            else
            {
                // 인덱스 증가시켜서 해당 블록 밑에 놓음
                MAP[++idx][j] = current;
            }
        }
    }
}
// 전체 블록 아래로 이동
// (열과 헹 번호만 다를뿐, up함수와 로직 똑같음)
void down()
{
    for (int j = 0; j < N; j++)
    {
        int idx = N - 1;
        for (int i = N - 1; i >= 0; i--)
        {
            if (MAP[i][j] != 0)
            {
                num.push(MAP[i][j]);
                MAP[i][j] = 0;
            }
        }
        while (!num.empty())
        {
            int current = num.front();
            num.pop();
            if (MAP[idx][j] == 0)
            {
                MAP[idx][j] = current;
            }
            else if (MAP[idx][j] == current)
            {
                MAP[idx--][j] *= 2;
            }
            else
            {
                MAP[--idx][j] = current;
            }
        }
    }
}
// 전체 블록 왼쪽으로 이동
void left()
{
    for (int i = 0; i < N; i++)
    {
        int idx = 0;
        for (int j = 0; j < N; j++)
        {
            if (MAP[i][j] != 0)
            {
                num.push(MAP[i][j]);
                MAP[i][j] = 0;
            }
        }
        while (!num.empty())
        {
            int current = num.front();
            num.pop();
            if (MAP[i][idx] == 0)
            {
                MAP[i][idx] = current;
            }
            else if (MAP[i][idx] == current)
            {
                MAP[i][idx++] *= 2;
            }
            else
            {
                MAP[i][++idx] = current;
            }
        }
    }
}
// 전체 블록 오른쪽으로 이동
void right()
{
    for (int i = 0; i < N; i++)
    {
        int idx = N - 1;
        for (int j = N - 1; j >= 0; j--)
        {
            if (MAP[i][j] != 0)
            {
                num.push(MAP[i][j]);
                MAP[i][j] = 0;
            }
        }
        while (!num.empty())
        {
            int current = num.front();
            num.pop();
            if (MAP[i][idx] == 0)
            {
                MAP[i][idx] = current;
            }
            else if (MAP[i][idx] == current)
            {
                MAP[i][idx--] *= 2;
            }
            else
            {
                MAP[i][--idx] = current;
            }
        }
    }
}
// dfs로 완전탐색 수행
void dfs(int cnt)
{
    int MAP_copy[MAX][MAX];
    // 5번 이동하면 가장 큰 블록의 값 구함
    if (cnt == 5)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                answer = max(answer, MAP[i][j]);
            }
        }
        return;
    }
    // 원래 보드 상태를 임시 배열에 복사해놓음
    copy(MAP, MAP_copy);

    for (int i = 0; i < 4; i++)
    {
        // 전체 블록을 상하좌우로 이동
        if (i == 0)
        {
            up();
        }
        else if (i == 1)
        {
            down();
        }
        else if (i == 2)
        {
            left();
        }
        else
        {
            right();
        }
        dfs(cnt + 1);
        // 임시 배열 상태를 보드에 저장
        copy(MAP_copy, MAP);
    }
}

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }

    dfs(0);

    cout << answer;

    return 0;
}