[baekjoon] 12100

2048 (Easy) 

문제

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

입력

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

 

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

예제 입력

3
2 2 2
4 4 4
8 8 8

예제 출력

16

풀이

최대 5번만 이동할 수 있기때문에 모든 경우를 돌려보면 될 것 같다.

회전 -> 이동 -> 회전(원위치)하면 4방향 모두 한번에 처리할 수 있다.

 

#include <iostream>
#include <string.h>

using namespace std;

int n, answer;

void printBoard(int ** board){
    for(int y = 0; y < n; y++){
        for(int x = 0; x < n; x++){
            cout << board[y][x] << " ";
        }
        cout << "\n";
    }  
}

void calcMax(int ** board){
    for(int y = 0; y < n; y++){
        for(int x = 0; x < n; x++){
            if(answer < board[y][x])answer = board[y][x];
        }
    }
}


void spinBoard(int ** board, int time)
{
    int **temp;

    temp = new int *[n];
    for(int i = 0; i < n; i++)temp[i] = new int[n];

    
    for(int t = 0; t < time; t++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++)temp[i][j] = board[n - j -1][i];
        }
        //copy
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++)board[i][j] = temp[i][j];
        }
    }
    
}

void moveBoard(int ** beforeBoard, int ** afterBoard, int direction)
{
    for(int y = 0; y < n; y++){
        for(int x = 0; x < n; x++){
            afterBoard[y][x] = beforeBoard[y][x];
        }
    }

    //방향에 따라 회전
    spinBoard(afterBoard, direction);
    
    //이동
    int * temp = new int[n];
    for(int y = 0; y < n; y++){
        int index = n - 1;
        memset(temp, 0, sizeof(int)*n);

        for(int x = n - 1; x >= 0; x--){
            if(temp[index] == 0){
                temp[index] = afterBoard[y][x];
            }
            else if(temp[index] == afterBoard[y][x]){
                temp[index] = temp[index] + afterBoard[y][x];
                index--;
            }else if(afterBoard[y][x] != 0){
                index--;
                temp[index] = afterBoard[y][x];
            }
        }
        for(int x = n - 1; x >= 0; x--)afterBoard[y][x] = temp[x];

    }
    //다시 회전해서 원래대로
    spinBoard(afterBoard, 4 - direction);
}


void func2048(int ** board, int round, int direction)
{
    //end
    if(round == 5){
        calcMax(board);
        return;
    }
    int ** afterBoard;
    

    afterBoard = new int *[n];
    for(int y = 0; y < n; y++){
        afterBoard[y] = new int[n];
    }
    

    moveBoard(board, afterBoard, direction);
    //ㅏ 오른쪽
    func2048(afterBoard, round+1, 0);
    //ㅗ  위
    func2048(afterBoard, round+1, 1);
    //ㅓ  왼쪽
    func2048(afterBoard, round+1, 2);
    //ㅜ  아래
    func2048(afterBoard, round+1, 3);
}

int main()
{
    int **board;
    
    cin >> n;

    board = new int *[n];

    for(int y = 0; y < n; y++){
        board[y] = new int[n];
        for(int x = 0; x < n; x++){
            cin >> board[y][x];
        }
    }

    if(n == 1){
        cout << board[0][0];
        return 0;
    }
    for(int i = 0; i < 4; i++){
        //func2048(board, 0, i);
    }
    cout << answer;
}