[백준] 12100번 2048 (Easy)

문제

https://www.acmicpc.net/problem/12100

풀이

제일 싫어하는 구현문제다. 중간에 큐 사용에 대한 오류가 떴는데 중단점을 이상한 곳으로 찍어놓고 디버깅을 돌려서 해결하는데 너무너무 오래걸렸다.

위, 아래, 왼쪽, 오른쪽 모든 방향을 Dfs를 통해 완전탐색하면 되는 문제다.

문제의 핵심은 주어진 조건에 맞게 한 쪽 방향으로 이동한 경우를 만드는 점이다.

똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.

이와 같은 조건 때문에 0이 아닌 수를 큐에 저장하는 순서는 아래와 같이 된다.

방향이 위인 경우 (0,0) ~ (N-1,0)
방향이 아래인 경우 (N-1,0) ~ (0,0)
방향이 왼쪽인 경우 (0,0) ~ (N-1,0)
방향이 오른쪽인 경우 (N-1,0) ~ (0,0)

각 경우에서 큐에 저장된 수와 현재 배열을 확인하여 블록을 합칠지 말지를 결정한다.

소스코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX_SIZE 21
#define MIN_INF -987654321

#define LEFT 0
#define RIGHT 1
#define UP 2
#define DOWN 3

int ans = MIN_INF;
int n;
int board[MAX_SIZE][MAX_SIZE];


void ChangeBoard(int direction)
{
    queue<int> q;

    switch (direction)
    {
        case UP:

            for (int col = 0; col < n; col++)
            {
                for (int row = 0; row < n; row++)
                {
                    if (board[row][col] != 0)
                    {
                        q.push(board[row][col]);
                        board[row][col] = 0;
                    }    
                }

                int idx = 0;
                while (!q.empty())
                {
                    int block = q.front();
                    q.pop();

                    if (board[idx][col] == 0)
                        board[idx][col] = block;
                    else if (board[idx][col] == block)
                    {
                        board[idx][col] *= 2;
                        idx++;
                    }
                    else
                        board[++idx][col] = block;
                }
            }
            break;

        case DOWN:

            for (int col = 0; col < n; col++)
            {
                for (int row = n - 1; row >= 0; row--)
                {
                    if (board[row][col] != 0)
                    {
                        q.push(board[row][col]);
                        board[row][col] = 0;
                    }
                }
                int idx = n-1;
                while (!q.empty())
                {
                    int block = q.front();
                    q.pop();

                    if (board[idx][col] == 0)
                        board[idx][col] = block;
                    else if (board[idx][col] == block)
                    {
                        board[idx][col] *= 2;
                        idx--;
                    }
                    else
                        board[--idx][col] = block;
                }
            }
            break;
        case LEFT:

            for (int row = 0; row < n; row++)
            {
                for (int col = 0; col < n; col++)
                {
                    if (board[row][col] != 0)
                    {
                        q.push(board[row][col]);
                        board[row][col] = 0;
                    }
                }
                int idx = 0;
                while (!q.empty())
                {
                    int block = q.front();
                    q.pop();

                    if (board[row][idx] == 0) 
                        board[row][idx] = block;
                    else if (board[row][idx] == block)
                    {
                        board[row][idx] *= 2;
                        idx++;
                    }
                    else
                        board[row][++idx] = block;
                }
            }
            break;
        case RIGHT:

            for (int row = 0; row < n; row++)
            {
                for (int col = n - 1; col >= 0; col--)
                {
                    if (board[row][col] != 0)
                    {
                        q.push(board[row][col]);
                        board[row][col] = 0;
                    }
                }

                int idx = n-1;
                while (!q.empty())
                {
                    int block = q.front();
                    q.pop();

                    if (board[row][idx] == 0)
                        board[row][idx] = block;
                    else if (board[row][idx] == block)
                    {
                        board[row][idx] *= 2;
                        idx--;
                    }
                    else
                        board[row][--idx] = block;
                }
            }
            break;

    }

}

int FindMax()
{
    int ret_max = MIN_INF;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (ret_max < board[i][j]) ret_max = board[i][j];
        }
    }

    return ret_max;
}

void Dfs(int depth)
{
    // 5번 이동했으면 최대값 저장
    if ( depth == 5 )
    {
        ans = max(ans, FindMax());
        return;
    }

    int tmp_map[MAX_SIZE][MAX_SIZE];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            tmp_map[i][j] = board[i][j];

    for (int k = 0; k < 4; k++)
    {
        // 모든 방향으로 바꾼 경우 탐색
        ChangeBoard(k);
        Dfs(depth+1);
        // 원래 상태로 돌려준다
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                board[i][j] = tmp_map[i][j];
    }

}

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

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> board[i][j];
            ans = max(ans, board[i][j]);
        }
    }

    Dfs(0);

    cout << ans << "\n";

    return 0;
}