(백준 c++)12100 2048(Easy

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

 

deque를 이용.

모든 경우의 수를 검사해야 하기 때문에 brute force, dfs로 진행한다.

최대가 5번 이동이기 때문에 시간 초과는 걱정이 없다.

 

보드판, 현재 이동 횟수, 방향을 dfs 함수로 전달하면서 수행.

이중 for문을 이용해 방향에 따라 배열 접근을 다르게 해주면 된다.

 

위쪽 방향인 경우

위에서 아래로.

 

아래쪽 방향인 경우

아래에서 위로.

 

왼쪽 방향인 경우

왼쪽에서 오른쪽으로.

 

오른쪽 방향인 경우

오른쪽에서 왼쪽으로.

 

0이 아닌 수를 deque에 넣어주면서 숫자를 더해주면 된다.

숫자를 더할 때 이미 더해진 수를 확인하기 위해 bool형 변수를 이용한다.

 

마지막으로 각 방향에 따라 deque에 있는 수를 넣어주면 된다.

만약 deque가 비어있다면 0을 넣어주어 빈 칸을 채워주면 된다.

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int ans = 0;
int N;

void dfs(vector<vector<int>> tmp_board, int cnt, int direction){
    if(cnt > 5){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                ans = ans < tmp_board[i][j] ? tmp_board[i][j] : ans;
            }
        }
        return;
    }

    //0 = 위, 1 = 아래, 2 = 왼쪽, 3 = 오른쪽 방향으로 이동
    if(direction == 0){
        for(int j = 0; j < N; j++){
            deque<int> d;
            bool changed = false;

            for(int i = 0; i < N; i++){
                if(tmp_board[i][j] != 0){
                    if(d.empty()){
                        d.push_back(tmp_board[i][j]);
                    }
                    else{
                        if(d.back() == tmp_board[i][j]){
                            if(!changed){
                                d.pop_back();
                                d.push_back(tmp_board[i][j] * 2);
                                changed = true;
                            }
                            else{
                                d.push_back(tmp_board[i][j]);
                                changed = false;
                            }
                        }
                        else{
                            d.push_back(tmp_board[i][j]);
                            changed = false;
                        }
                    }
                }
                
            }

            for(int i = 0; i < N; i++){
                if(!d.empty()){
                    tmp_board[i][j] = d.front();
                    d.pop_front();
                }
                else{
                    tmp_board[i][j] = 0;
                }
            }
        }
    }
    else if(direction == 1){
        for(int j = 0; j < N; j++){
            deque<int> d;
            bool changed = false;

            for(int i = N - 1; i >= 0; i--){
                if(tmp_board[i][j] != 0){
                    if(d.empty()){
                        d.push_front(tmp_board[i][j]);
                    }
                    else{
                        if(d.front() == tmp_board[i][j]){
                            if(!changed){
                                d.pop_front();
                                d.push_front(tmp_board[i][j] * 2);
                                changed = true;
                            }
                            else{
                                d.push_front(tmp_board[i][j]);
                                changed = false;
                            }
                            
                        }
                        else{
                            d.push_front(tmp_board[i][j]);
                            changed = false;
                        }
                    }
                }
            }

            for(int i = N - 1; i >= 0; i--){
                if(!d.empty()){
                    tmp_board[i][j] = d.back();
                    d.pop_back();
                }
                else{
                    tmp_board[i][j] = 0;
                }
            }
        }
    }
    else if(direction == 2){
        for(int i = 0; i < N; i++){
            deque<int> d;
            bool changed = false;

            for(int j = 0; j < N; j++){
                if(tmp_board[i][j] != 0){
                    if(d.empty()){
                        d.push_back(tmp_board[i][j]);
                    }    
                    else{
                        if(d.back() == tmp_board[i][j]){
                            if(!changed){
                                d.pop_back();
                                d.push_back(tmp_board[i][j] * 2);
                                changed = true;
                            }
                            else{
                                d.push_back(tmp_board[i][j]);
                                changed = false;
                            }
                        }
                        else{
                            d.push_back(tmp_board[i][j]);
                            changed = false;
                        }
                    }
                }
            }

            for(int j = 0; j < N; j++){
                if(!d.empty()){
                    tmp_board[i][j] = d.front();
                    d.pop_front();
                }
                else{
                    tmp_board[i][j] = 0;
                }
            }
        }
    }
    else if(direction == 3){
        for(int i = 0; i < N; i++){
            deque<int> d;
            bool changed = false;

            for(int j = N - 1; j >= 0; j--){
                if(tmp_board[i][j] != 0){
                    if(d.empty()){
                      d.push_front(tmp_board[i][j]);
                    }
                    else{
                        if(d.front() == tmp_board[i][j]){
                            if(!changed){
                                d.pop_front();
                                d.push_front(tmp_board[i][j] * 2);
                                changed = true;
                            }
                            else{
                                d.push_front(tmp_board[i][j]);
                                changed = false;
                            }
                        }
                        else{
                            d.push_front(tmp_board[i][j]);
                            changed = false;
                        }
                    }
                }
            }

            for(int j = N - 1; j >= 0; j--){
                if(!d.empty()){
                    tmp_board[i][j] = d.back();
                    d.pop_back();
                }
                else{
                    tmp_board[i][j] = 0;
                }
            }
        }
    }
    
    dfs(tmp_board, cnt + 1, 0);
    dfs(tmp_board, cnt + 1, 1);
    dfs(tmp_board, cnt + 1, 2);
    dfs(tmp_board, cnt + 1, 3);
}

int main(void){
    cin >> N;
    
    vector<vector<int>> board(N, vector<int>(N, 0));

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> board[i][j];
        }
    }

    dfs(board, 1, 0);
    dfs(board, 1, 1);
    dfs(board, 1, 2);
    dfs(board, 1, 3);

    cout << ans;
    
    return 0;
}