백준 12100번 : 2048(Easy) (c++)

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

12100번: 2048 (Easy)

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

예제 입력
3
2 2 2
4 4 4
8 8 8

예제 출력
16

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int map[20][20];
int mapCopy[20][20];
int arr[5];
int res = 0;
/*
void moveleft();
void moveright();
void movedown();
*/
void moveup(){
    for(int j=0;j<N;j++){
        int cnt=0;
        for(int i=0;i<N;i++){
            if(map[i][j]!=0){
                int temp =map[i][j];
                map[i][j]=0;
                map[cnt][j]=temp;
                cnt++;
            }
        }

        for(int i=0;i<N-1;i++){
            if(map[i][j]==map[i+1][j]){
                map[i][j]*=2;
                map[i+1][j]=0;
            }
        }
        cnt=0;
        for(int i=0;i<N;i++){
            if(map[i][j]!=0){
                int temp =map[i][j];
                map[i][j]=0;
                map[cnt][j]=temp;
                cnt++;
            }
        }
    }
}
void moveleft(){
    for(int i=0;i<N;i++){
        int cnt=0;
        for(int j=0;j<N;j++){
            if(map[i][j]!=0){
                int temp =map[i][j];
                map[i][j]=0;
                map[i][cnt]=temp;
                cnt++;
            }
        }
        for(int j=0;j<N-1;j++){
            if(map[i][j]==map[i][j+1]){
                map[i][j]*=2;
                map[i][j+1]=0;
            }
        }
        cnt=0;
        for(int j=0;j<N;j++){
            if(map[i][j]!=0){
                int temp =map[i][j];
                map[i][j]=0;
                map[i][cnt]=temp;
                cnt++;
            }
        }
    }
}
void movedown(){
    for(int j=0;j<N;j++){
        int cnt=N-1;
        for(int i=N-1;i>=0;i--){
            if(map[i][j]!=0){
                int temp =map[i][j];
                map[i][j]=0;
                map[cnt][j]=temp;
                cnt--;
            }
        }
        for(int i=N-1;i>0;i--){
            if(map[i][j]==map[i-1][j]){
                map[i][j]*=2;
                map[i-1][j]=0;
            }
        }
        cnt=N-1;
        for(int i=N-1;i>=0;i--){
            if(map[i][j]!=0){
                int temp =map[i][j];
                map[i][j]=0;
                map[cnt][j]=temp;
                cnt--;
            }
        }
    }

}
void moveright(){
    for(int i=0;i<N;i++){
        int cnt=N-1;
        for(int j=N-1;j>=0;j--){
            if(map[i][j]!=0){
                int temp =map[i][j];
                map[i][j]=0;
                map[i][cnt]=temp;
                cnt--;
            }
        }
        for(int j=N-1;j>0;j--){
            if(map[i][j]==map[i][j-1]){
                map[i][j]*=2;
                map[i][j-1]=0;
            }
        }
        cnt=N-1;
        for(int j=N-1;j>=0;j--){
            if(map[i][j]!=0){
                int temp =map[i][j];
                map[i][j]=0;
                map[i][cnt]=temp;
                cnt--;
            }
        }
    }
}

void moving(){
    memcpy(map,mapCopy,sizeof(map));
    for(int i=0;i<5;i++){
        //0 위 1 오 2 아래 3왼
        int dir = arr[i];
        if(dir==0){
            moveup();
        }else if(dir==1){
            moveright();
        }else if(dir==2){
            movedown();
        }else if(dir==3){
            moveleft();
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]>res) {
                res=map[i][j];
            }
        }
    }
}
void simulation(int cnt){
    if(cnt==5){
        moving();
        return;
    }
    for(int i=0;i<4;i++){
        arr[cnt]=i;
        simulation(cnt+1);
    }
}

int main(){
    
    freopen("input.txt","r",stdin);

    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>map[i][j];
        }
    }
    
    memcpy(mapCopy,map,sizeof(map));

    simulation(0);

    cout<<res;

    return 0;
    
}