[백준(BOJ)] 12100번 : 2048(Easy) C++ 풀이(시뮬레이션, DFS)

접근:

사실상 구현을 잘하는지 묻는 문제.(덕분에 복붙의 향연을 볼 수 있었다..)

크기가 20x20 미만이므로 dfs(백트래킹)를 이용해서 풀어도 무방하다.

 

전략:

구현 부분은 대략적으로만 설명하면,

모듈화를 위해서 판에 있는 줄들을 한 줄씩 가져와서, 줄을 이동하는 좌우로 이동 가능한 함수를 만든다.

각 줄에 대해 이동을 한 후에 다시 복사하여 다음 count 에 해당하는 map 변수로 저장하여 다음 함수로 넘어간다.

(이렇게 따로 저장해 놓으면 따로 백트래킹 처리를 하지 않아도 된다)

 

그 외 5번 내로 가장 최대로 구할 수 있는 수를 구해야 하므로

DFS를 이용하여, 시뮬레이션을 진행한다.

그 후에 가장 큰 수를 map을 스캔 해서 가장 큰 것을 취하여 반환한다.

 

코드:

#include <iostream>
#include <queue>
#define MAX 5

using namespace std;
int n;

int map[MAX+1][20][20];
int line[20];

// down, right, up, left
void move(int dir){
    int temp = 0;

    if(dir == 0){ //왼쪽으로
        int insIdx = 0;

            for(int j=0;j<n;j++){
                if(line[j] == 0){ //빈공간
                    continue;
                }
                if(temp == line[j]){ //이전값하고 동일하면 합병
                    line[insIdx-1] *= 2;
                    line[j] = 0;
                    temp = 0; //초기화
                }else{ 
                    temp = line[j];
                    if(insIdx != j) {line[j] = 0;}
                    line[insIdx++] = temp;
                    
                    
                }
            }

    }else{ //오른쪽으로
        int insIdx = n-1;

        for(int j=n-1;j>=0;j--){

                if(line[j] == 0){ //빈공간
                    continue;
                }

                if(temp == line[j]){ //이전값하고 동일하면 합병
                    line[insIdx+1] *= 2;
                    line[j] = 0;
                    temp = 0; //초기화
                }else{ 
                    temp = line[j];
                    if(insIdx != j) {line[j] = 0;}
                    line[insIdx--] = temp;
                    
                    
                }
            }
    }
}

int solve(int count){ // dfs
    if(count == 0){
        int mx = 0;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(mx < map[0][i][j]) mx = map[0][i][j];
            }
        }

       
        return mx;

    }else{
        int res = 0;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                line[j] = map[count][j][i];
            }
            //up
            move(0);

            for(int j=0;j<n;j++){
                map[count-1][j][i] = line[j];
            }
        }
        print(count-1);
        res = max(res, solve(count-1));

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                line[j] = map[count][j][i];
            }
            //down
            move(1);

            for(int j=0;j<n;j++){
                map[count-1][j][i] = line[j];
            }
        }print(count-1);
        res = max(res, solve(count-1));

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                line[j] = map[count][i][j];
            }
            //left
            move(0);

            for(int j=0;j<n;j++){
                map[count-1][i][j] = line[j];
            }
        }print(count-1);
        res = max(res, solve(count-1));

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                line[j] = map[count][i][j];
            }
            //right
            move(1);

            for(int j=0;j<n;j++){
                map[count-1][i][j] = line[j];
            }
        }print(count-1);
        res = max(res, solve(count-1));

       return res;
    }       

}
int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> map[MAX][i][j];
        }
    }

   cout << solve(MAX);

    return 0;
}