[백준][브루트포스][구현][백트래킹] 12100 2048 c++구현

목차

https://www.acmicpc.net/problem/12100

문제

 

문제 구현 방향 및 아이디어

생각보다 어려웠다. 아이디어는 슬라이드를 어떻게 하든 90도 돌리면 결과는 같다는 것이다.

따라서 회전하는 횟수에 따라서 슬라이드를 반복하는 재귀를 잘 구현하면 되는 문제였다.

 

 

1. 90도 회전 아이디어

아래와 같이 하면 90도 회전을 구현할 수있다.

void rotate(int board[41][41]) {
    int temp[41][41] = { 0 };
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = board[N - 1 - j][i];
        }
    }
    memcpy(board, temp, sizeof(temp));
}

 

2. 슬라이디 아이디어

90도 회전할 것이기 때문에 한 방향만 구현해 주면 된다.

void slide(int board[41][41]) {
    int temp[41][41] = { 0 };

    for (int i = 0; i < N; i++) {
        int cnt = 0;
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 0)
                continue;
            if (temp[i][cnt] == 0) {
                temp[i][cnt] = board[i][j];
            }
            else if (temp[i][cnt] == board[i][j]) {
                temp[i][cnt] *= 2;
                cnt++;
            }
            else {
                cnt++;
                temp[i][cnt] = board[i][j];
            }
            
        }
    }
    memcpy(board, temp, sizeof(temp));
}

 

3. 재귀에 관한 아이디어

이게 생각하는게 가장 어려웠다...

원상복구가 아니기 때문에 회전한 횟수에 따라 배열을 복사해 놓고 슬라이드를 진행시킨 후 재귀를 돌리면 된다.

void game(int here, int board[41][41]) {
    if (here == 5) {
        counting(board);
        return;
    }
    
    for (int i = 0; i < 4; i++) {
        int cpy[41][41] = { 0 };
        memcpy(cpy, board, sizeof(cpy));
        slide(cpy);
        game(here + 1, cpy);
        rotate(board);
    }
    return;
}

 

코드 구현

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<math.h>
#include<stack>

using namespace std;

int N;
int sum = 0;

void rotate(int board[41][41]) {
    int temp[41][41] = { 0 };
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = board[N - 1 - j][i];
        }
    }
    memcpy(board, temp, sizeof(temp));
}

void slide(int board[41][41]) {
    int temp[41][41] = { 0 };

    for (int i = 0; i < N; i++) {
        int cnt = 0;
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 0)
                continue;
            if (temp[i][cnt] == 0) {
                temp[i][cnt] = board[i][j];
            }
            else if (temp[i][cnt] == board[i][j]) {
                temp[i][cnt] *= 2;
                cnt++;
            }
            else {
                cnt++;
                temp[i][cnt] = board[i][j];
            }
            
        }
    }
    memcpy(board, temp, sizeof(temp));
}

void counting(int board[41][41]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sum = max(sum, board[i][j]);
        }
    }
}

void game(int here, int board[41][41]) {
    if (here == 5) {
        counting(board);
        return;
    }
    
    for (int i = 0; i < 4; i++) {
        int cpy[41][41] = { 0 };
        memcpy(cpy, board, sizeof(cpy));
        slide(cpy);
        game(here + 1, cpy);
        rotate(board);
    }
    return;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int board[41][41] = { 0 };
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    game(0, board);

    cout << sum;
    
}