본문 바로가기
백준 문제풀이

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

by 꽁이꽁설꽁돌 2024. 8. 13.
728x90
반응형

목차

    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;
        
    }
    반응형