[ 백준 12094 ] 2048 (Hard) (C++)

백준의 2048(Hard)(12094) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

2048(Easy)(12100) 문제와 똑같지만, 최대로 움직일 수 있는 횟수가 10번으로 더 많다.

12100번 문제와 똑같이 중복순열을 통해 단순 완전탐색으로 구현하게 된다면 시간초과를 받게 된다.

본인도 시간초과를 해결하지 못해서 다른 분들의 생각을 조금 참고해서 해결했다.

이 문제는 '탐색할 필요가 없는 경우' 를 끝까지 탐색해보지 않고 중간에 탐색을 멈춰버리는 백트래킹을 구현해 주어야 한다.

그럼 어떤 경우에는 탐색을 더 이상 해볼 필요가 없는지 알아보자.

1. 맵을 특정 방향으로 움직였을 때, 맵의 변화가 존재하지 않는 경우

먼저탐색을 끝까지 해보지 않아도 되는 첫 번째 경우이다.

예를 들어서 아래와 같은 맵이 있다고 생각해보자.

( 맵의 일부만 간단하게 가져왔다고 가정. 주어지는 맵은 N x N 크기의 맵입니다. )

위의 경우에서 맵을 오른쪽 방향으로 기울이는 것이 과연 의미가 있을지 생각해보자.

오른쪽 방향으로 기울이더라도, 합쳐지는 숫자가 없기 때문에 그 결과가 위의 맵과 동일할 것이다.

더 나아가서, 오른쪽 방향으로만 10번을, 혹은 왼쪽 방향으로만 10번을 탐색하는 경우가 과연 필요할까 ??

불필요한 탐색이다.

즉, 맵을 특정 방향으로 움직였을 때, 맵의 변화가 존재하지 않는다면, 끝까지 탐색을 해볼 필요가 없다.

이 조건만으로는 시간초과를 면하기 어렵다. 그래서 한 가지 더 걸러주어야 한다.

2. 현재 나온 최댓값으로 기존의 최대값을 갱신할 수 없는 경우

예를 들어서 현재까지 탐색을 한 경우, 최댓값이 2048 이라고 가정해보자. 지금까지 우리가 구한 최댓값은 2048이다.

이제 그 다음 탐색을 진행하는데, 다음과 같은 상황을 생각해보자.

"현재 1번 움직여봤는데, 현재까지의 최댓값으로 2가 나왔습니다."

이 상황이다. 그럼, 우리가 어떤 방향으로 움직일지, 맵이 어떤 상태인지, 어떻게 맵이 변할지는 직접 해봐야 알겠지만

정말로 맵이 최고의 상황이라고 생각해보자.

여기서 최고의 상황이라는 것은 "움직일 때마다, 퍼즐들이 합쳐져서 계속해서 최댓값이 갱신되는 상황" 을 의미한다.

그럼, 현재 한번 움직였을 때 '2' 였다. 지금부터 10번을 간단하게만 계산을 해보자. 지금부터는 무조건 어떤 방향으로 움직일지, 맵이 어떤 상태인지를 떠나서 무조건 퍼즐을 기울일 때 마다 숫자가 합쳐진다고 가정하자.

그럼 두 번째 움직임에 의해서 최댓값이 '4'가 될 것이다.

세 번째 움직임에 의해서 최댓값이 '8'이 될 것이다.

네 번째 움직임에 의해서 최댓값이 '16'이 될 것이다.

다 섯번째 움직임에 의해서 최댓값이 '32'가 될 것이다.

.... 마지막 10번째 움직임에 의해서 최댓값이 '1024' 가 될 것이다.

최고의 상황이라고 가정하고 맵을 움직여봤는데, 최댓값이 '1024'로, 우리가 기존에 구해놨던 '2048'에 비해서 작은 값이다.

따라서, 값이 갱신되지 않는다. 결과적으로만 본다면, 최댓값이 갱신되지 않기 때문에 탐색을 하지 않을 수 있었다면,

하지 않는게 좋은 탐색 과정이다.

우리는 지금부터 이 경우를 걸러줄 것이다. 탐색을 하지 않을 것이다.

위의 상황을 다시 처음부터 차근차근 확인하면서 알아가보자.

처음에 움직인 횟수가 '0'인 상태에서, 한번 움직였더니, 최댓값이 '2'가 나온 상태였다.

그럼 이제부터 움직일 수 있는 횟수는 '9'번 남게된다. (한번 움직였으므로 !)

그럼 9번 남은 상태에서, 현재 최댓값이 '2'다. 이것만으로 '1024'라는 숫자를 한번에 구해보자.

먼저 결론부터 말하자면, "움직였을 때의 최댓값 x 2^남은횟수" 이다.

한번 위의 식에 대입해보자. 움직였을 때의 최댓값 = 2 . 2^남은횟수 = 2^9 = 512.

따라서 현재 탐색으로 기대해볼 수 있는 최댓값 = 2 x 512 = 1024 가 된다.

위의 공식이 맞는지 간단하게 한번만 확인해보자. "내가 현재 3번 움직였고, 지금까지의 최댓값이 4다. 기대해볼 수 있는

최댓값은 ?"

움직였을 때의 최댓값 = 4

남은 횟수 = 7회

따라서, 4 * 2^7 = 4 * 128 = 512

직접해보자.

3번째 움직임에 의해서 최댓값 = 4

4번째 움직임에 의해서 최댓값 = 8

5번째 움직임에 의해서 최댓값 = 16

(6)32 / (7)64 / (8)128 / (9) 256 / (10) 512

이렇게 현재 몇번 움직였고, 현재 까지 나온 최댓값으로 기대해볼 수 있는 최댓값을 추측할 수 있고, 그 최댓값이

우리가 기존에 구해놓은 최댓값보다 크지 않다면, 더 이상 탐색을 할 필요가 없다.

물론, 우리는 지금 최고의 상황이라고 가정을 하고 기대할 수 있는 최댓값을 구해봤을 뿐, 실제로 계속해서 탐색을

하다보면 기대했던 최댓값만큼 나오지 않고 중간에 탐색이 중단될 수도 있다.

하지만 ! 최고의 상황이라고 기대했을 때에도, 기존의 최댓값보다 더 큰 값이 나오지 않는데, 과연 최고의 상황이 아닐 때

기존의 최댓값보다 더 큰 값이 나올 수 있을까 ?? 절대 나올 수가 없다.

따라서 위와 같은 상황에서는 탐색을 해 볼 필요가 없다 !

본인이 구현한 백트래킹은 위의 2가지 이다.

처음에 이 2가지를 구현하고 제출을 했더니, 시간초과가 또 발생하게 되었다. 위의 로직에는 문제가 없었지만,

중간중간 계속해서 맵을 바꿔주는 과정과 해당 맵에서 최댓값을 찾는 과정에서 시간이 오래걸렸다.

그래서, 맵을 바꿔주는 과정도 최대한 간단하게 만들어보았고, 그 간단하게 만들면서 최댓값을 바로바로 계산해 주었다.

( 기존에는 맵 바꿔주는 과정과 맵에서 최대값을 찾는 과정을 따로따로 구현했었음 )

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, Answer;
int MAP[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];
            if (MAP[i][j] > Answer) Answer = MAP[i][j];
        }
    }
}
 
void Copy_MAP(int A[][MAX], int B[][MAX])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            A[i][j] = B[i][j];
        }
    }
}
 
int Move(int Dir, int A[][MAX])
{
    int Max_Value = 0;
    if (Dir == 0)
    {
        for (int i = 0; i < N; i++)
        {
            int Value = -1;
            int Idx = N;
 
            for (int j = N - 1; j >= 0; j--)
            {
                if (A[i][j] == 0) continue;
                if (A[i][j] == Value)
                {
                    A[i][Idx] = A[i][Idx] * 2;
                    Value = -1;
                }
                else
                {
                    Value = A[i][j]; Idx--;
                    A[i][Idx] = A[i][j];
                }
 
                Max_Value = Bigger(Max_Value, A[i][Idx]);
            }
 
            for (int j = Idx - 1; j >= 0; j--) A[i][j] = 0;
        }
    }
    else if (Dir == 1)
    {
        for (int i = 0; i < N; i++)
        {
            int Value = -1;
            int Idx = -1;
 
            for (int j = 0; j < N; j++)
            {
                if (A[i][j] == 0) continue;
 
                if (A[i][j] == Value)
                {
                    A[i][Idx] = A[i][Idx] * 2;
                    Value = -1;
                }
                else
                {
                    Value = A[i][j]; Idx++;
                    A[i][Idx] = A[i][j];
                }
 
                Max_Value = Bigger(Max_Value, A[i][Idx]);
            }
 
            for (int j = Idx + 1; j < N; j++) A[i][j] = 0;
        }
    }
    else if (Dir == 2)
    {
        for (int j = 0; j < N; j++)
        {
            int Value = -1;
            int Idx = N;
 
            for (int i = N - 1; i >= 0; i--)
            {
                if (A[i][j] == 0) continue;
 
                if (A[i][j] == Value)
                {
                    A[Idx][j] = A[Idx][j] * 2;
                    Value = -1;
                }
                else
                {
                    Value = A[i][j]; Idx--;
                    A[Idx][j] = A[i][j];
                }
 
                Max_Value = Bigger(Max_Value, A[Idx][j]);
            }
 
            for (int i = Idx - 1; i >= 0; i--) A[i][j] = 0;
        }
    }
    else if (Dir == 3)
    {
        for (int j = 0; j < N; j++)
        {
            int Value = -1;
            int Idx = -1;
 
            for (int i = 0; i < N; i++)
            {
                if (A[i][j] == 0) continue;
 
                if (A[i][j] == Value)
                {
                    A[Idx][j] = A[Idx][j] * 2;
                    Value = -1;
                }
                else
                {
                    Value = A[i][j]; Idx++;
                    A[Idx][j] = A[i][j];
                }
 
                Max_Value = Bigger(Max_Value, A[Idx][j]);
            }
 
            for (int i = Idx + 1; i < N; i++) A[i][j] = 0;
        }
    }
    return Max_Value;
}
 
bool Same_MAP(int A[][MAX], int B[][MAX])
{
    /* 같은 맵인지 확인하는 함수 */
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (A[i][j] != B[i][j]) return false;
        }
    }
    return true;
}
 
bool Have_Possible(int Next_Max, int Next_Cnt)
{
    /* 현재 움직인 횟수와 최대값을 통해서, 최고의 상황에서의 기댓값을 계산. */
    int Remain_Cnt = 10 - Next_Cnt;
    int Expect_Max = Next_Max * pow(2, Remain_Cnt);
    
    if (Answer >= Expect_Max) return false;
    return true;
}
 
void DFS(int Cnt, int State[][MAX], int Max_Value)
{
    if (Cnt == 10)
    {
        Answer = Max_Value;
        return;
    }
 
    for (int i = 0; i < 4; i++)
    {
        int nState[MAX][MAX];
        int nMax_Value;
        int nCnt = Cnt + 1;
 
        Copy_MAP(nState, State);
        nMax_Value = Move(i, nState);
 
        if (Same_MAP(State, nState) == true) continue;
        if (Have_Possible(nMax_Value, nCnt) == true) DFS(nCnt, nState, nMax_Value);
    }
}
 
void Solution()
{
    DFS(0, MAP, Answer);
    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;
}