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

백준의 2048(Easy)(12100) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 조금 까다로운 시뮬레이션 문제이다. 천천히 단계별로 알아가보도록 하자.

    먼저 우리는 방향을 선택해줘야 한다. 최대 5번을 이동해서 만들 수 있을 때, 어느 방향으로 보드에 있는 숫자들을

    움직일 것인지를 결정해주어야 한다.

    만약 5번중에 첫번째로 동쪽으로 움직여 줬다고 생각해보자. 그럼 두번째는 어느방향으로 움직여줄 수 있을까?

    동서남북 4방향 중에 어떤방향이든 가능하다. 세번째 네번째 다섯번째도 모두 마찬가지이다.

    즉, { 1번째 움직임, 2번째 움직임, 3번째 움직임, 4번째 움직임, 5번째 움직임 } 을 나타내면

    { 동동동동동 } , { 동동동동서 } , { 동동동동남 } , { 동동동동북 } .... { 북북북북남 } , { 북북북북북 } 과 같은 경우가 쭉

    나열될 것이다.

    이거를 어떻게 구할 수 있을까?? 바로 중복순열이다. 일단 뭐 같은 방향이 여러분 나올 수 있다는 것에서 중복이라는 것을

    알겠는데 왜 순열인지 알아보자.

    보드를 동쪽으로 움직이고 서쪽으로 움직이는 것과 서쪽으로 움직이고 동쪽으로 움직이는 것의 결과가 같을까 ??

    아니다 다를 것이다.

    이러한 맵이 있다고 생각해보자. (그냥 간략하게 가져온 것입니다. NxN 으로 주어진다는 것 알고

     알고있습니다.)

     이 때, 동쪽으로 움직이고 서쪽으로 움직인 후의 보드의 상황과 서쪽으로 움직이고 동쪽으로 움직였을 때의 보드의 상태

     는 어떨까 ??

    

    아마 위의 그림과 같을 것이다. 위의 그림에서 위에 있는 그림은 동쪽으로 움직이고 서쪽으로 움직인 경우, 밑에 그림이

    서쪽으로 움직이고 동쪽으로 움직이는 경우이다.

    보면 보드의 상태가 서로 다르다는 것을 알 수 있다. 즉, 우리는 순서에 영향을 미치는 중복적으로 선택이 가능한 중복순열을

    구현해 주면 된다. 중복 순열을 아직 잘 모른다면 아래의 글을 읽고 오도록 하자.

    [ 중복순열 알아보기(Click) ]

2) 중복순열을 통해서 이제 방향을 모두 정해주었다면 보드를 실제로 움직이면서 합칠 걸 합쳐주기만 하면 된다.

   합쳐주는 부분은 사실은 특별한 알고리즘이 사용되지는 않아서 그냥 본인이 합친 방법만 설명하고 끝내겠다.

   먼저 방법은 총 3단계로 나뉜다. (보드를 오른쪽으로 움직인다고 가정하고 진행하겠습니다.)

   1. 같은 숫자끼리 합쳐주고 뭐고 그런거 없이 무조건 보드를 싹다 오른쪽으로 옮겨준다.

     이런식으로 바뀌게 !

   2. 이제 가장 오른쪽부터 현재 자기 좌표 - 1 한 값과 값이 같은지 체크한 후에 같다면 더해주고 칸을 없애는 일을 해준다.

    이런식으로 !

     보면 그림이 조금 이상하다. 왜 저렇게 했을까?? 바로 한번 합쳐진 블럭은 또 합쳐질 수 없다는 조건 때문이다.

     가장 윗줄인 (0 , 2 , 4, 4)로 이해해보자. 가장 오른쪽부터 현재 자기좌표 -1 한 값과 비교한다고 했다.

     즉, (0, 3)의 4와 (0, 2)의 4를 비교해서 같은 값이므로 (0, 3)을 8로 만들어주고 (0, 2)를 0으로 만들어 줌으로써 빈칸으로

     만들어 주었다. 그 다음 (0, 2)과 (0, 1)을 비교해보자. (0, 2)는 위의 과정에서 0이 되었으므로 (0, 1)과 다르기 때문에 넘어간다.

     이런식으로 계산을 해주면 한번 합쳐진 블럭은 절대로 또 다시 합쳐지지 않는다.

     하지만 여기서 끝내버리면 안된다. 1 번에서 했던 과정을 한번 더 반복함으로써 맵의 전체 숫자들을 다시 오른쪽으로 옮겨

     줘야 한다.

    이렇게 되도록 !

이 후, 맵 전체를 탐색하면서 최댓값을 찾아주고 또 다른 중복순열을 통해 나온 수열들로 계산을 반복해주면 된다.

물론, 맵을 계속 움직여주고 합쳐주고 없애주고 해야 하기 때문에 맵 복사를 반드시 해줘야 한다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
int C_MAP[MAX][MAX];
int Select[5];
bool Visit[MAX][MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Copy_MAP()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            C_MAP[i][j] = MAP[i][j];
        }
    }
}
 
void Move_Left()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N - 1; j++)
        {
            bool Check = false;
            if (C_MAP[i][j] == 0)
            {
                int k = j + 1;
                while (k <= N - 1)
                {
                    if (C_MAP[i][k] != 0)
                    {
                        Check = true;
                        break;
                    }
                    k++;
                }
                if (Check == true)
                {
                    C_MAP[i][j] = C_MAP[i][k];
                    C_MAP[i][k] = 0;
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N - 1; j++)
        {
            if (C_MAP[i][j] == C_MAP[i][j + 1])
            {
                C_MAP[i][j] = C_MAP[i][j] * 2;
                C_MAP[i][j + 1] = 0;
            }
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N - 1; j++)
        {
            bool Check = false;
            if (C_MAP[i][j] == 0)
            {
                int k = j + 1;
                while (k <= N - 1)
                {
                    if (C_MAP[i][k] != 0)
                    {
                        Check = true;
                        break;
                    }
                    k++;
                }
                if (Check == true)
                {
                    C_MAP[i][j] = C_MAP[i][k];
                    C_MAP[i][k] = 0;
                }
            }
        }
    }
}
 
void Move_Right()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = N - 1; j > 0; j--)
        {
            bool Check = false;
            if (C_MAP[i][j] == 0)
            {
                int k = j - 1;
                while (k >= 0)
                {
                    if (C_MAP[i][k] != 0)
                    {
                        Check = true;
                        break;
                    }
                    k--;
                }
                if (Check == true)
                {
                    C_MAP[i][j] = C_MAP[i][k];
                    C_MAP[i][k] = 0;
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = N - 1; j > 0; j--)
        {
            if (C_MAP[i][j] == C_MAP[i][j - 1])
            {
                C_MAP[i][j] = C_MAP[i][j] * 2;
                C_MAP[i][j - 1] = 0;
            }
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = N - 1; j > 0; j--)
        {
            bool Check = false;
            if (C_MAP[i][j] == 0)
            {
                int k = j - 1;
                while (k >= 0)
                {
                    if (C_MAP[i][k] != 0)
                    {
                        Check = true;
                        break;
                    }
                    k--;
                }
                if (Check == true)
                {
                    C_MAP[i][j] = C_MAP[i][k];
                    C_MAP[i][k] = 0;
                }
            }
        }
    }
}
 
void Move_Up()
{
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < N; j++)
        {
            bool Check = false;
            if (C_MAP[i][j] == 0)
            {
                int k = i + 1;
                while (k <= N - 1)
                {
                    if (C_MAP[k][j] != 0)
                    {
                        Check = true;
                        break;
                    }
                    k++;
                }
 
                if (Check == true)
                {
                    C_MAP[i][j] = C_MAP[k][j];
                    C_MAP[k][j] = 0;
                }
            }
        }
    }
 
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (C_MAP[i][j] == C_MAP[i + 1][j])
            {
                C_MAP[i][j] = C_MAP[i][j] * 2;
                C_MAP[i + 1][j] = 0;
            }
        }
    }
 
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j < N; j++)
        {
            bool Check = false;
            if (C_MAP[i][j] == 0)
            {
                int k = i + 1;
                while (k <= N - 1)
                {
                    if (C_MAP[k][j] != 0)
                    {
                        Check = true;
                        break;
                    }
                    k++;
                }
 
                if (Check == true)
                {
                    C_MAP[i][j] = C_MAP[k][j];
                    C_MAP[k][j] = 0;
                }
            }
        }
    }
}
 
void Move_Down()
{
    for (int i = N - 1; i > 0; i--)
    {
        for (int j = 0; j < N; j++)
        {
            bool Check = false;
            if (C_MAP[i][j] == 0)
            {
                int k = i - 1;
                while (k >= 0)
                {
                    if (C_MAP[k][j] != 0)
                    {
                        Check = true;
                        break;
                    }
                    k--;
                }
                if (Check == true)
                {
                    C_MAP[i][j] = C_MAP[k][j];
                    C_MAP[k][j] = 0;
                }
            }
        }
    }
 
    for (int i = N - 1; i > 0; i--)
    {
        for (int j = 0; j < N; j++)
        {
            if (C_MAP[i - 1][j] == C_MAP[i][j])
            {
                C_MAP[i][j] = C_MAP[i][j] * 2;
                C_MAP[i - 1][j] = 0;
            }
        }
    }
    for (int i = N - 1; i > 0; i--)
    {
        for (int j = 0; j < N; j++)
        {
            bool Check = false;
            if (C_MAP[i][j] == 0)
            {
                int k = i - 1;
                while (k >= 0)
                {
                    if (C_MAP[k][j] != 0)
                    {
                        Check = true;
                        break;
                    }
                    k--;
                }
                if (Check == true)
                {
                    C_MAP[i][j] = C_MAP[k][j];
                    C_MAP[k][j] = 0;
                }
            }
        }
    }
 
}
 
int Find_Max()
{
    int Max = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (C_MAP[i][j] > Max)
            {
                Max = C_MAP[i][j];
            }
        }
    }
    return Max;
}
 
void Play_The_Game()
{
    for (int i = 0; i < 5; i++)
    {
        int Dir = Select[i];
        if (Dir == 0) Move_Right();
        else if (Dir == 1) Move_Left();
        else if (Dir == 2) Move_Down();
        else if (Dir == 3) Move_Up();
    }
 
    Answer = Bigger(Answer, Find_Max());
}
 
void Select_Direction(int Idx, int Cnt)
{
    if (Cnt == 5)
    {
        Copy_MAP();
        Play_The_Game();
        return;
    }
 
    for (int i = 0; i < 4; i++)
    {
        Select[Cnt] = i;
        Select_Direction(i, Cnt + 1);
    }
}
 
void Solution()
{
    Select_Direction(0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}