12100번-2048(easy)

문제

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

12100번: 2048 (Easy)

---

접근방법

1) 접근 사고

1.상하좌우로 기울이는 모든 경우를 DFS로 탐색

2.이때 탐색이 5가 되면 배열중 가장 큰 값을 찾고 비교해준다.

 

2) 시간 복잡도

O(n ^ 2)

 

3) 실수

1. 113번째 줄에서 처음에 memcpy를 사용하여 배열의 복사와 갱신을 진행해주려고 하였다. 그러나 DFS 재귀함수에 매개변수 배열을 넘겨서 재귀함수 상태에서 배열의 사이즈는 int *의 자료형이므로 내가 원하는 sizeof (MAX *MAX)가 아니라 sizeof(4)라 정상정적인 복사가 되지 않는다. 

 

4) PS

안 좋은 습관을 찾을 수 있게 해주었던 문제다. 재귀함수를 진행할 때 C++의 array나 vector를 사용하는것이 좋다는 결론을 얻게 되었다. 배열을 매개변수로 넘기는것은 위험하다는것을 알게 되었고 좀 더 C++스러운 문법을 사용하는것이 좋을거같다.

---

정답 코드

#include<bits/stdc++.h>

using namespace std;
const int MAX = 21;

int my[] = {-1, 0, 1, 0};
int mx[] = {0, 1, 0, -1};

struct game{
    int n;
    int ret;
    int board[MAX][MAX];
    game(int n) : n(n), ret(0) {}

    bool isValid(int y, int x){
        return y >= 0 && y < n && x >= 0 && x < n;
    }

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

    void move(int tmpboard[MAX][MAX], int dir){
        int tmptmpboard[MAX][MAX];
        memset(tmptmpboard, 0 ,sizeof tmptmpboard);
        if(dir == 0){ //북
            for(int i = 0; i < n; i++){
                int posIdx = 0;
                for(int j = 0; j < n; j++)
                    if(tmpboard[j][i]){
                        if(tmptmpboard[posIdx][i] == 0){
                            tmptmpboard[posIdx][i] = tmpboard[j][i];
                        }
                        else if(tmptmpboard[posIdx][i] == tmpboard[j][i]){
                            tmptmpboard[posIdx++][i] *= 2;
                        }
                        else{
                            tmptmpboard[++posIdx][i] = tmpboard[j][i];
                        }
                    }
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    tmpboard[i][j] = tmptmpboard[i][j];
                }
            }
        }
        else if(dir == 1){ //동
            for(int i = 0; i < n; i++){
                int posIdx = n - 1;
                for(int j = n - 1; j >= 0; j--)
                    if(tmpboard[i][j]){
                        if(tmptmpboard[i][posIdx] == 0){
                            tmptmpboard[i][posIdx] = tmpboard[i][j];
                        }
                        else if(tmptmpboard[i][posIdx] == tmpboard[i][j]){
                            tmptmpboard[i][posIdx--] *= 2;
                        }
                        else{
                            tmptmpboard[i][--posIdx] = tmpboard[i][j];
                        }
                    }
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    tmpboard[i][j] = tmptmpboard[i][j];
                }
            }
        }
        else if(dir == 2){//남
            for(int i = 0; i < n; i++){
                int posIdx = n - 1;
                for(int j = n - 1; j >= 0; j--)
                    if(tmpboard[j][i]){
                        if(tmptmpboard[posIdx][i] == 0){
                            tmptmpboard[posIdx][i] = tmpboard[j][i];
                        }
                        else if(tmptmpboard[posIdx][i] == tmpboard[j][i]){
                            tmptmpboard[posIdx--][i] *= 2;
                        }
                        else{
                            tmptmpboard[--posIdx][i] = tmpboard[j][i];
                        }
                    }
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    tmpboard[i][j] = tmptmpboard[i][j];
                }
            }
        }
        else if(dir == 3){//서
            for(int i = 0; i < n; i++){
                int posIdx = 0;
                for(int j = 0; j < n; j++)
                    if(tmpboard[i][j]){
                        if(tmptmpboard[i][posIdx] == 0){
                            tmptmpboard[i][posIdx] = tmpboard[i][j];
                        }
                        else if(tmptmpboard[i][posIdx] == tmpboard[i][j]){
                            tmptmpboard[i][posIdx++] *= 2;
                        }
                        else{
                            tmptmpboard[i][++posIdx] = tmpboard[i][j];
                        }
                    }
            }

            //memcpy(tmpboard, tmptmpboard, sizeof tmpboard); , 사용하면 오류 발생 왜냐하면 매개변수를 포인터로 배열로 넘겨서 tmpboard의 자료형은 4이다
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    tmpboard[i][j] = tmptmpboard[i][j];
                }
            }
        }
    }

    void DFS(int board[MAX][MAX], int level){
        if(level == 5){
            ret = max(getMaxValue(board), ret);
            return ;
        }
        int tmpboard[MAX][MAX];
        memcpy(tmpboard, board, sizeof tmpboard);

        for(int d = 0; d < 4; d++){
            move(tmpboard, d);
            DFS(tmpboard, level + 1);
            memcpy(tmpboard, board, sizeof tmpboard);
        }
    }

    int getMaxValue(int board[MAX][MAX]){
        int ret = INT_MIN;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++){
                ret = max(ret, board[i][j]);
            }
        return ret;
    }

    void printBoard(int board[MAX][MAX]){
        for(int i = 0; i < n; i++){
            for(int j =0 ; j < n; j++){
                cout << board[i][j] << " ";
            }
            cout <<"\n";
        }
        cout << "=================" <<"\n";
    }
};
int main(){
    int n;
    cin >> n;
    game op(n);
    op.init();
    op.DFS(op.board, 0);
    cout << op.ret <<"\n";
}​