[BOJ] 12100 2048(Easy)

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

12100번: 2048 (Easy)

이 문제를 풀면서 가장 어려웠던 것은 현재 상태를 저장하는 이중배열을 만드는 것이었다.

함수가 호출 될 때마다, 이중포인터에 공간을 할당하여 이중배열을 만든 뒤 전에 있던 상태를 저장해 주었다.

그 외에 막혔던 부분은 

2 2 4 0 0 일 경우 왼쪽으로 움직이면 4 4 0 0 0 이 되어야 하는데 8 0 0 0 0이 되게 구현을 해놓아서 check이라는 배열을 이용하여 이동 중에 한 번 변형되었다면 다시는 변형되지 못하게 처리하여 해결하였다.

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#define MAX 5;
using namespace std;

//int map[20][20];
int move_map[20][20];
bool check[20][20];
int direction[4];
int N,ans=0;

void up(int** map){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]==0) continue;
            int pos=i;
            while(pos>0){
                if(map[pos-1][j]==map[pos][j]&&!check[pos-1][j]){
                    map[pos-1][j]*=2;
                    check[pos-1][j]=true;
                    map[pos][j]=0;
                    break;
                }
                if(map[pos-1][j]==0){
                    map[pos-1][j]=map[pos][j];
                    map[pos][j]=0;
                    pos--;
                }else{
                    break;
                }
            }
        }
    }
}

void down(int** map){
    for(int i=N-1;i>=0;i--){
        for(int j=0;j<N;j++){
            if(map[i][j]==0) continue;
            int pos=i;
            while(pos<N-1){
                if(map[pos+1][j]==map[pos][j]&&!check[pos+1][j]){
                    map[pos+1][j]*=2;
                    check[pos+1][j]=true;
                    map[pos][j]=0;
                    break;
                }
                if(map[pos+1][j]==0){
                    map[pos+1][j]=map[pos][j];
                    map[pos][j]=0;
                    pos++;
                }else{
                    break;
                }
            }
        }
    }
}

void left(int** map){
    for(int j=0;j<N;j++){
        for(int i=0;i<N;i++){
            if(map[i][j]==0) continue;
            int pos=j;
            while(pos>0){
                if(map[i][pos-1]==map[i][pos]&&!check[i][pos-1]){
                    map[i][pos-1]*=2;
                    check[i][pos-1]=true;
                    map[i][pos]=0;
                    break;
                }
                if(map[i][pos-1]==0){
                    map[i][pos-1]=map[i][pos];
                    map[i][pos]=0;
                    pos--;
                }else{
                    break;
                }
            }
        }
    }
}

void right(int** map){
    for(int j=N-1;j>=0;j--){
        for(int i=0;i<N;i++){
            if(map[i][j]==0) continue;
            int pos=j;
            while(pos<N-1){
                if(map[i][pos+1]==map[i][pos]&&!check[i][pos+1]){
                    map[i][pos+1]*=2;
                    check[i][pos+1]=true;
                    map[i][pos]=0;
                    break;
                }
                if(map[i][pos+1]==0){
                    map[i][pos+1]=map[i][pos];
                    map[i][pos]=0;
                    pos++;
                }else{
                    break;
                }
            }
        }
    }
}


void copy_map(int** map, int** copy){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) copy[i][j]=map[i][j];
    }
}


void cal(int n,int** map){
    if(n==5){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                ans=max(ans,map[i][j]);
            }
        }
        return;
    }
    
    int** copy=(int**)malloc(sizeof(int*)*N);
    for(int i=0;i<N;i++){
        copy[i]=(int*)malloc(sizeof(int)*N);
    }
    copy_map(map,copy);
    
    for(int i=0;i<4;i++){
        copy_map(map,copy);
        fill(&check[0][0],&check[19][20],false);
        if(i==0){
            up(copy);
            cal(n+1,copy);
        }
        else if(i==1){
            down(copy);
            cal(n+1,copy);
        }else if(i==2){
            left(copy);
            cal(n+1,copy);
        }else if(i==3){
            right(copy);
            cal(n+1,copy);
        }
    }
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int **map;
    cin>>N;
    map=(int**)malloc(sizeof(int*)*N);
    for(int i=0;i<N;i++){
        map[i]=(int*)malloc(sizeof(int)*N);
    }
    
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++){
            int x;
            cin>>x;
            map[i][j]=x;
            ans=max(ans,map[i][j]);
        }
    
    cal(0,map);
    cout<<ans;
    return 0;
}