[백준 12100][C++] 2048(Easy) (Gold 2)

[문제보기]

 12100. 2048(Easy)

12100번: 2048 (Easy)

[풀이과정]

 (1) main()

      입력값을 map배열에 입력받아 dfs()로 던지는 부분이다. 

 

 (2) calculation(int type)

      if문을 사용하여 각 type에 해당하는 연산을 진행해주는데 주석에 쓰인 것처럼 0은 좌, 1은 우, 2는 상, 3은 하를 

      뜻한다.

      연산에 대한 내용은 queue를 만들어서 map에 있는 값을 queue에 담고, 다 0으로 바꿔준다.

      q가 비어있을 때까지 while() 문을 수행하는데, queue.front() 값을 data에 넣고, map에 넣어주는 방식이다. 

      넣어줄 때, idx 변수를 하나 만들어서 map에 값을 넣어주는데 현재 보고 있는 map의 위치의 값이 0이면 data를

      넣어주고, 값이 있다면 data값과 비교를 하여 같은 값이면 map의 값을 *2를 해주고, 다른 값이면 그다음 위치에 

      data를 넣는다. 

 

      각 type에 따라 map을 바라보는 순서가 달라질 뿐, 그 안의 구체적인 연산은 동일하다

 

 (3) dfs(int cnt)

      cnt는 몇 번 이동을 했는지에 대한 의미를 가지고 있다. 문제에서 최대 5번이라고 하였으므로 cnt가 5가 되면

      get_max() 함수를 통해 map에서 최대 숫자를 찾아 return 해준다. 이때 return으로 받은 최대 숫자와 ans의 값을 

      비교하여 더 큰 값을 ans에 업데이트시켜준다.

 

      현재 map의 정보를 temp 배열을 만들어 저장해준다.

   

      상, 하, 좌, 우로 움직일 수 있는 경우가 4번이므로 for문을 통해 4번 반복해준다. for문안에서 값을 입력받아         

      calculation()을 수행해준다. 수행 후 dfs()를 다시 불러준다.

      연산을 하고 난 뒤 map을 원상 복구해주기 위해 미리 temp에 저장해놓은 값을 map에 다시 넣어주고, for문을 

      수행해준다.

 

[소스보기]

#include <iostream>
#include <queue>

#define size 20
using namespace std;
int map[size][size];
int n, ans = 0;

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

void calculation(int type){
   queue<int> q;

    //좌
    if(type == 0){
        for(int i=0; i<n; i++){
            for(int j=n-1; j>=0; j--){
                if(map[i][j])
                    q.push(map[i][j]);
                map[i][j] = 0;
            }

            int idx = n-1;

            while(!q.empty()){
                int data = q.front();
                q.pop();

                if(map[i][idx] == 0){
                    map[i][idx] = data;
                }
                else if(map[i][idx] == data){
                    map[i][idx] *= 2;
                    idx--;
                }
                else{
                    idx--;
                    map[i][idx] = data;
                }
            }
        }

    }

    //우
    if(type == 1){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j])
                    q.push(map[i][j]);
                map[i][j] = 0;
            }

            int idx = 0;

            while(!q.empty()){
                int data = q.front();
                q.pop();

                if(map[i][idx] == 0){
                    map[i][idx] = data;
                }
                else if(map[i][idx] == data){
                    map[i][idx] *= 2;
                    idx++;
                }
                else{
                    idx++;
                    map[i][idx] = data;
                }
            }
        }
    }

    //상
    if(type == 2){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[j][i])
                    q.push(map[j][i]);
                map[j][i] = 0;
            }

            int idx = 0;

            while(!q.empty()){
                int data = q.front();
                q.pop();

                if(map[idx][i] == 0){
                    map[idx][i] = data;
                }
                else if(map[idx][i] == data){
                    map[idx][i] *= 2;
                    idx++;
                }
                else{
                    idx++;
                    map[idx][i] = data;
                }
            }
        }
    }

   //하
    if(type == 3){
        for(int i = 0; i<n; i++){
            for(int j = n-1; j>=0; j--){
                if(map[j][i])
                    q.push(map[j][i]);
                map[j][i] = 0;
            }

            int idx = n-1;

            while(!q.empty()){
                int data = q.front();
                q.pop();

                if(map[idx][i] == 0){
                    map[idx][i] = data;
                }
                else if(map[idx][i] == data){
                    map[idx][i] *= 2;
                    idx--;
                }
                else{
                    idx--;
                    map[idx][i] = data;
                }
            }

        }
    }
}

void dfs(int cnt){
    if(cnt == 5){
        ans = max(ans, get_max());
        return;
    }

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

    for(int i=0; i<4; i++){
        calculation(i);
        dfs(cnt+1);
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j] = temp[i][j];
            }
        }
        
    }
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);

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

    dfs(0);

    cout << ans << "\n";
    return 0;
}

 

[해결과정 중 실수한 부분]

 

[참고한 자료]

https://jaimemin.tistory.com/660