(C++) - 백준(BOJ) 12100번 : 2048(Easy)

www.acmicpc.net/problem/12100

12100번: 2048 (Easy)

Easy?? 하지 못한 시뮬레이션 문제였습니다.

 

풀이방법

 1. 각 합치는 방향을 0,1,2,3(상,우,좌,하)으로 생각했을 때 4진법으로 5번의 이동을 4^5의 수로 표현할 수 있습니다.

 

 2. 합칠 때 합친 결과를 출력할 필요가 없으므로 돌린뒤 위쪽방향으로 합치는 것으로 가정합니다. 어떤 이동의 방향이 0이라면 돌리지 않습니다. 방향이 1이라면 90도 오른쪽으로 돌린 뒤 위로 합칩니다. 2라면 90도 오른쪽으로 두 번 돌린 뒤 위로 합칩니다. 이 방식으로 굳이 여러방향으로 돌리는 것을 골치아프게 생각하지 않아도 됩니다.

j번째 이동의 합치는 방향(회전 수)는 전체 이동 정보 i % 4입니다. 이 값으로 돌리는 횟수를 switch case문으로 정하시면 됩니다.

 

 3. 모두 돌렸으면 이제 합칩니다. 합치는 알고리즘은 다음과 같습니다.

  3-1. 하나의 열을 떼서 가져와 확인할 vector변수를 선언합니다.

  3-2. 이 vector에 0이 아닌 모든 칸을 push_back해줍니다. vector의 한 원소는 그 인덱스가 곧 행을 의미하게 됩니다.

  3-3. 현재 행이 다음 행과 값이 같다면 두 값을 합친 뒤 queue에 넣어줍니다. 그 후 queue에는 이미 정보가 담겨있으므로 현재 행과 다음 행의 값을 0으로 지워줍니다. 합칠 수는 없으나 현재 값이 있는 경우에도 push해줍니다.

  3-1 ~ 3-3 의 단계를 모든 열에 대해 수행해줍니다.

 

합친 열의 정보를 가지고 있는 queue가 있으므로 기존의 board를 모두 지워줍니다.

그 후 queue를 하나씩 꺼내서 해당하는 칸에 값을 넣어줘 갱신해줍니다.

 

4. 합친 후 가장 큰 칸의 값을 ans 변수에 저장합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair <int,int>;
//이동 중 이미 합쳐진 블록은 바로 또 합칠 수 없다
int n, ans;
int board[21][21];
int boardCopy[21][21];
int stat[5];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
//dir = 0 : 상, 1 : 우, 2 : 하, 3 : 좌로 이동
void moveBlock(){
    queue <pii> q; //값,열
    int isCombined[21][21];
    memset(isCombined,0,sizeof(isCombined));
    for(int i = 0; i < n; i++){
        vector <int> v;
        for(int j = 0; j < n; j++){
            if(boardCopy[j][i]) v.push_back((boardCopy[j][i]));
        }

        for(int j = 0; j < v.size(); j++){
            if(j < v.size()-1 && v[j] != 0 && v[j] == v[j+1] ){
                q.push({v[j] + v[j+1],i});
                v[j] = 0, v[j+1] = 0;
                j++;
            }
            if(v[j])
                q.push({v[j],i});
        }
    }
    //q에 다 저장되어 있음
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            boardCopy[i][j] = 0;
        }
    }
    //boardCopy에 바뀐 값 저장
    int rowPivot = 0; //지금 어떤 행 할 차례다 알려주는 용도
    int colPivot = 0; //지금 어떤 열 할 차례다 알려주는 용도
    while(!q.empty()){
        int val = q.front().first;
        int col = q.front().second;
        q.pop();
        if(colPivot != col) {colPivot = col,rowPivot = 0;}
        boardCopy[rowPivot++][col] = val;
    }
}

void copyBoard(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            boardCopy[i][j] = board[i][j];
        }
    }
}

int getMaxBlock(){
    int big = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            big = max(big,boardCopy[i][j]);
    return big;
}

void rotateBoardCopy(){
    int tmp[21][21];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            tmp[i][j] = boardCopy[n-1-j][i];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            boardCopy[i][j] = tmp[i][j];
        }
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> board[i][j];
        }
    }
    //각 이동 방향은 0,1,2,3으로 표현됨
    //i번째 이동의 이동 방향은 1 2 1 2 1 이런식으로 표현
    //i번째 이동 방향 구하고 이동하기
    
    for(int i = 0; i < 1 << (2 * 5); i++){
        copyBoard();
        int moveStat = i;
        for(int j = 0; j < 5; j++){
            int rotateNum = moveStat % 4;
            moveStat /= 4;
            switch(rotateNum){
                //상우하좌 case 0할필요없음
                case 1:
                rotateBoardCopy();
                break;

                case 2:
                rotateBoardCopy();
                rotateBoardCopy();
                break;

                case 3:
                rotateBoardCopy();
                rotateBoardCopy();
                rotateBoardCopy();
                break;
            }
            moveBlock();
        }
        ans = max(ans,getMaxBlock());

    }
    cout << ans <<'\n';
}

 

 

Test Case

몇 가지 테스트 케이스를 직접 작성해봤습니다.

 

4
2 4 2 8
8 4 0 0 
16 8 2 0
2 8 2 0 
32

 

4
2 4 16 8
8 4 0 0
16 8 1 0
2 8 2 0
32

 

4
16 16 16 8
16 4 0 0
16 8 0 0
2 8 2 0
64

 

4
2 4 16 8
8 0 0 0 
16 8 0 0
2 8 2 0 
64

 

4
2 4 16 8
8 0 0 0 
16 8 0 0
2 8 2 0 
64