BOJ 12100 2048 (Easy)

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

보드를 이동시켰을 때 보드위의 숫자들을 합하는 것이 관건인 문제였다.

 

나는 보드 위의 행 혹은 열을 vector v에 담아 넘겨주면, 그것을 이동시켜주는 merge  함수를 구현하였고, 이동에 따라 v에 담는 순서를 다르게 하여 merge함수에 넘겨주었고, 알아서 합쳐주게 하였다.

그것만 구현한다면, 방향에 따른 처리 순서는 인덱스 처리 문제여서 크게 문제될 것이 없다.

 

코드는 다음과 같다.

#include <cstdio>
#include <vector>

using namespace std;

enum{
    up = 0,
    down,
    left,
    right
};

const int command_count = 5;
int command[5];
int n;
int board[20][20];


vector<int> merge(vector<int> v){
    vector<int> merged(n, 0);
    int now_index = 0;
    for(int num : v){
        if(num == 0) continue;
        else if(merged[now_index] == 0) merged[now_index] = num;
        else if(num == merged[now_index]){
            merged[now_index] += num;
            now_index += 1;
        }
        else{
            now_index += 1;
            merged[now_index] = num;
        }
    }
    return merged;
}


int DFS(int now){
    if(now == command_count){
        int m = 0;

        int tboard[20][20]={0,};
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                tboard[i][j] = board[i][j];
            }
        }

        for(int a=0;a<command_count;a++){

            if(command[a] == up){
                for(int i=0;i<n;i++){
                    vector<int> v(n, 0);
                    for(int j=0;j<n;j++){
                        v[j] = tboard[j][i];
                    }
                    vector<int> merged = merge(v);
                    for(int j=0;j<n;j++){
                        tboard[j][i] = merged[j];
                    }
                }
            }

            if(command[a] == down){
                for(int i=0;i<n;i++){
                    vector<int> v(n, 0);
                    for(int j=n-1;j>=0;j--){
                        v[n-1-j] = tboard[j][i];
                    }
                    vector<int> merged = merge(v);
                    for(int j=n-1;j>=0;j--){
                        tboard[j][i] = merged[n-1-j];
                    }
                }
            }

            if(command[a] == left){
                for(int i=0;i<n;i++){
                    vector<int> v(n, 0);
                    for(int j=0;j<n;j++){
                        v[j] = tboard[i][j];
                    }
                    vector<int> merged = merge(v);
                    for(int j=0;j<n;j++){
                        tboard[i][j] = merged[j];
                    }
                }
            }

            if(command[a] == right){
                for(int i=0;i<n;i++){
                    vector<int> v(n, 0);
                    for(int j=n-1;j>=0;j--){
                        v[n-1-j] = tboard[i][j];
                    }
                    vector<int> merged = merge(v);
                    for(int j=n-1;j>=0;j--){
                        tboard[i][j] = merged[n-1-j];
                    }
                }
            }

        }
        //printf("\n\n");

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                //printf("%d ",tboard[i][j]);
                if(tboard[i][j]> m){
                    m = tboard[i][j];
                }
            }
            //printf("\n");
        }
        return m;
    }

    int a = 0;
    for(int i=0;i<4;i++){
        command[now] = i;
        int t = DFS(now+1);
        if(t > a ) a = t;
    }
    return a;
}


int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&(board[i][j]));
        }
    }

    printf("%d\n",DFS(0));

    return 0;
}

 

이동 방향에 따라 인덱스 처리를 다르게 해주는 부분이 굉장히 코드적으로 중복된다는 생각이 들었고, 함수 내의 vector 선언때문에 시간을 많이 잡아먹을것같다고 생각이 들었지만, 머리를 굴려봐도 방법이 떠오르지 않아 제출을 하였다.

정답을 받긴했어도 찝찝했다.

 

 

다른 사람들은 굉장히 짧은 코드로 정답을 받아냈는데, 1등코드를 보니 배열의 회전을 통해 내가 생각했던 코드 중복 부분을 엄청 줄이셨다. 

 

구현 문제도 코드 최적화 부분이 많은 요소를 차지하는 만큼 만만히 봐서는 안될 것같다.