[백준] 2048(Easy)(12100)

문제 링크 : [백준] 2048(Easy)(12100)

문제 설명

2048 게임판이 주어 질 때, 최대 5번 움직여서 얻을 수 있는 최대수를 구하세요.

입력

N(게임판의 크기, 1 <= N <=20)
N_ij(게임판 구성, 0 : 빈칸, 2^k, 1 <= k <= 10)

3
2 2 2
4 4 4
8 8 8

출력

16

카테고리

#브루트포스 #구현

시간 복잡도 상한

꽤 커도 될 것 같습니다.

해결 방법

1. 모든 경우의 수를 계산해보면 4⁵(한번 이동에 네방향이 있고, 최대 다섯번 이동 가능)이고
2. 한 경우에서, 전체 판을 두, 세번정도 탐색해야 되기 때문에, 1024 * 5 * 5 * 3 정도의 시간복잡도가 나올 것 같습니다.
3. 즉, 다 돌려도 시간이 초과되지 않습니다.
4. 주의할 점은 빈 칸이 있을 경우, 빈칸에 대한 처리가 있어야 합니다.
   4-1. 한 방향으로 움직이기 전에 빈칸을 모두 제거
   4-2. 움직인 후, 합쳐진 칸들에 대한 빈 칸 처리도 해주어야 합니다.
5. 아래 코드는 너무 복잡합니다. 앞으로 코드를 깔끔하게 짜는 노력을 해야할 것 같습니다.

시간복잡도

O(4^N * N²)

코드

#include<cstdio>
#include<string.h>
#include<algorithm>
#define cp for(int i=1;i<=n;i++)memcpy(z[i],x[i],sizeof(x[i]));
#define S 22
using namespace std;
int n,d[S][S],i,j,k,a;
void up(int arr[][S]){
    for(int i=1;i<n;i++){
        for(int j=1;j<=n;j++){
            if(!arr[i][j])continue;
            int k=i+1;
            while(!arr[k][j]&&k<=n)k++;
            if(arr[k][j]==arr[i][j]){
                arr[i][j]*=2;
                arr[k][j]=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!arr[i][j]){
                int k=i;
                while(!arr[k][j]&&k<=n)k++;
                arr[i][j]=arr[k][j];
                arr[k][j]=0;
            }
        }
    }
}
void down(int arr[][S]){
    for(int i=n;i>1;i--){
        for(int j=1;j<=n;j++){
            if(!arr[i][j])continue;
            int k=i-1;
            while(!arr[k][j]&&k)k--;
            if(arr[k][j]==arr[i][j]){
                arr[i][j]*=2;
                arr[k][j]=0;
            }
        }
    }
    for(int i=n;i;i--){
        for(int j=1;j<=n;j++){
            if(!arr[i][j]){
                int k=i;
                while(!arr[k][j]&&k)k--;
                arr[i][j]=arr[k][j];
                arr[k][j]=0;
            }
        }
    }
}
void left(int arr[][S]){
    for(int i=1;i<n;i++){
        for(int j=1;j<=n;j++){
            if(!arr[j][i])continue;
            int k=i+1;
            while(!arr[j][k]&&k<=n)k++;
            if(arr[j][k]==arr[j][i]){
                arr[j][i]*=2;
                arr[j][k]=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!arr[i][j]){
                int k=j;
                while(!arr[i][k]&&k<=n)k++;
                arr[i][j]=arr[i][k];
                arr[i][k]=0;
            }
        }
    }
}
void right(int arr[][S]){
    for(int i=n;i>1;i--){
        for(int j=1;j<=n;j++){
            if(!arr[j][i])continue;
            int k=i-1;
            while(!arr[j][k]&&k)k--;
            if(arr[j][k]==arr[j][i]){
                arr[j][i]*=2;
                arr[j][k]=0;
            }
        }
    }
    for(int i=n;i;i--){
        for(int j=1;j<=n;j++){
            if(!arr[j][i]){
                int k=i;
                while(!arr[j][k]&&k)k--;
                arr[j][i]=arr[j][k];
                arr[j][k]=0;
            }
        }
    }
}
int r(int p,int x[][S]){
    if(!p){
        int q=0;
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)q=max(q,x[i][j]);
        return q;
    }
    int z[S][S],q;
    memset(z,0,sizeof(z));
    cp
    up(z);
    q=r(p-1,z);
    cp
    down(z);
    q=max(q,r(p-1,z));
    cp
    left(z);
    q=max(q,r(p-1,z));
    cp
    right(z);
    q=max(q,r(p-1,z));
    return q;
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",d[i]+j);
    printf("%d",r(5,d));
}