12100. 2048 (Easy) GOLD II (C++)

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

12100번: 2048 (Easy)

 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int MAP[20][20],temp[20][20], ans,n;
int mx[] = {-1,1,0,0}, my[] = {0,0,-1,1}; //u,d,l,r
vector<int> Vdir;
 
int check()
{
    queue<int> q;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            temp[i][j] = MAP[i][j];
    for(int i=0;i<5;i++)
    {
        int dir = Vdir[i];
        switch (dir)
        {
        case 0: //u
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(temp[j][i] != 0)
                    {
                        q.push(temp[j][i]);
                        temp[j][i] = 0;
                    }
                }
                int idx = 0;
                while(q.size() > 1)
                {
                    temp[idx][i] = q.front();
 
                    q.pop();
                    if(temp[idx][i] == q.front())
                    {
                        q.pop();
                        temp[idx][i] *= 2;
                    }
                    idx++;
                }
                if(!q.empty()){
                    temp[idx][i] = q.front();
                    q.pop();
                }
            }
            break;
 
        case 1: //d
            for(int i=0;i<n;i++)
            {
                for(int j= n - 1;j>=0;j--)
                {
                    if(temp[j][i] != 0)
                    {
                        q.push(temp[j][i]);
                        temp[j][i] = 0;
                    }
                }
                int idx = n - 1;
                while(q.size() > 1)
                {
                    temp[idx][i] = q.front();
 
                    q.pop();
                    if(temp[idx][i] == q.front())
                    {
                        q.pop();
                        temp[idx][i] *= 2;
                    }
                    idx--;
                }
                if(!q.empty()){
                    temp[idx][i] = q.front();
                    q.pop();
                }
            }
 
            break;
        case 2: //left
            for(int i=0;i<n;i++)
            {
                for(int j= 0;j<n;j++)
                {
                    if(temp[i][j] != 0)
                    {
                        q.push(temp[i][j]);
                        temp[i][j] = 0;
                    }
                }
                int idx = 0;
                while(q.size() > 1)
                {
                    temp[i][idx] = q.front();
 
                    q.pop();
                    if(temp[i][idx] == q.front())
                    {
                        q.pop();
                        temp[i][idx] *= 2;
                    }
                    idx++;
                }
                if(!q.empty()){
                    temp[i][idx] = q.front();
                    q.pop();
                }
            }
 
 
            break;
        case 3: //right
            for(int i=0;i<n;i++)
            {
                for(int j= n-1;j>=0;j--)
                {
                    if(temp[i][j] != 0)
                    {
                        q.push(temp[i][j]);
                        temp[i][j] = 0;
                    }
                }
                int idx = 0;
                while(q.size() > 1)
                {
                    temp[i][idx] = q.front();
 
                    q.pop();
                    if(temp[i][idx] == q.front())
                    {
                        q.pop();
                        temp[i][idx] *= 2;
                    }
                    idx++;
                }
                if(!q.empty()){
                    temp[i][idx] = q.front();
                    q.pop();
                }
 
            }
 
            break;
 
        }
    }
    int ret = 0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(temp[i][j] > ret)
                ret = temp[i][j];
 
    return ret;
}
int solve()
{
    int ret = 0;
    for(int aa=0;aa<4;aa++)
    {
        Vdir.push_back(aa);
        for(int bb=0;bb<4;bb++)
        {
            Vdir.push_back(bb);
            for(int cc =0;cc<4;cc++)
            {
                Vdir.push_back(cc);
                for(int dd = 0; dd<4;dd++)
                {
                    Vdir.push_back(dd);
                    for(int ee=0;ee<4;ee++)
                    {
                        Vdir.push_back(ee);
                        int a = check();
                        ret = ret > a ? ret : a;
                        Vdir.pop_back();
                    }
                    Vdir.pop_back();
                }
                Vdir.pop_back();
            }
            Vdir.pop_back();
        }
        Vdir.pop_back();
    }
 
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>MAP[i][j];
    cout<<solve();
    return 0;
}
 

음... 조금 방향 설정하는게 너저분하긴 하다.

5번 돌렸을 때 최대값을 찾는 것인데 횟수가 늘어날수록 크기가 커지면 커졌지 줄어들지는 않으니 5번 다 돌린다음에 최대값을 찾으면 된다. 그래서 중간에 확인하는 과정이 필요없다.

 

벡터에 5개 넣는것은 이제 재귀로도 짤 수 있었는데 for문 쓰는게 직관적이어서 저렇게 했다.

그런데 너저분하네

 

돌리는 과정은 이렇다.

1. 먼저 원조 배열을 복사한 배열을 생성한다.

2. 5방향으로 돌린다.

 

돌리는 매커니즘은 위쪽 방향만 설명하겠다. 다른 방향은 다 똑같은 매커니즘으로 하면 된다.

위쪽으로 움직이는 것은 열을 움직이는 것이기 때문에 각 열의 값들을 queue에 집어 넣으면서 0으로 바꿔준다.

 

맨 위부터 queue에 front값을 넣어주는데 같은 숫자 2개일 때 합쳐진다고 했으므로 

이 때 다음 queue의 front값과 동일하면 현재 값을 X2 해주고 queue를 한 번더 pop 해준다.

 

위 과정을 모든 열에 대해서 실행한다. 

다른 방향도 위와 같은 매커니즘으로 돌리면 된다.

 

이걸 돌리고 최대값을 찾아 답을 구해주면 된다.