[백준][C++] 12100번: 2048 (Easy) <215>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

12100번: 2048 (Easy)

생각의 흐름

원래 맨 처음 생각한 풀이는 DFS를 진행하면서 우선 방향에 대한 중복순열을 구한 후, 구해논 중복 순열대로 돌려가면서 닶을 구하려 했다.

문제는 4방위에 맞도록 비슷한 함수를 4번이나 작성해야 한다는 점 이였다....

 

이러한 문제를 해결하기 위해 2차원 배열 자체를 90' 씩 회전시키면서 구하는 방법을 선택하게 되었다.

90도를 돌리는 아이디어는 다른 블로그 글을 읽고 알아냈다!

 

다음이 90도 회전시키는 함수이다.

void rotation(int arr[][21]) {
    int temp[21][21];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            temp[j][N - 1 - i] = arr[i][j];
    memcpy(arr, temp, sizeof(temp));
}

인자로 받은 2차원 배열 arr을 시계방향으로 90도 돌려주는 함수이다.

 

이를 활용해서 BFS를 진행한다.

void DFS(int cnt) {
    if(cnt == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(res < MAP[i][j]) res = MAP[i][j];
            }
        }
        return;
    }

    int temp[21][21];
    for(int i = 0; i < 4; i++) {
        memcpy(temp, MAP, sizeof(MAP)); // origin -> copy
        move(MAP);
        DFS(cnt + 1);
        memcpy(MAP, temp, sizeof(MAP)); // copy -> origin
        rotation(MAP);
    }
}

BFS의 depth가 5에 도달하면 결과를 갱신해주면 되는 부분은 당연하다.

 

이후 4방위에 대하여 한번씩 돌리는 부분이 핵심이다.

1) MAP -> temp로 배열을 복사한다.

2) 원본의 MAP을 한 방향으로 이동시킨다.

3) 다음 DFS로 이동

4) temp를 다시 MAP으로 복사한다.

5) MAP을 90도 돌린다.

 

여기서 MAP을 왜 temp에 복사 해 두는지 궁금할수 있다.

temp에 복사 해 두지 않으면, move한 결과의 배열을 90도 돌리게 된다.

우리는 하나의 원본 배열을 기준으로 4방위로 이동시켜 봐야 한다.

즉 원본인 MAP을 기준으로 4방위로 이동시켜야 하는데, MAP을 한번 이동시킨 Move된 MAP을 가지고 돌리면 이상한 결과가 나온다.

 

따라서 이동시키기 전에 원본을 저장 한 후, 방향을 돌리기전 다시 복사해주어야 한다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;

int N;
int MAP[21][21];
int res;

void move(int arr[][21]) {
    for(int i = 0; i < N; i++) {
        deque<int> dq;
        bool isAlreadyMerge = false;
        for(int j = 0; j < N; j++) {
            if(arr[i][j] != 0) {
                if(!dq.empty() && dq.back() == arr[i][j] && isAlreadyMerge == false){
                    dq.pop_back();
                    dq.push_back(arr[i][j] * 2);
                    isAlreadyMerge = true;
                }else{
                    dq.push_back(arr[i][j]);
                    isAlreadyMerge = false;
                }
                arr[i][j] = 0;
            }
        }

        int index = 0;
        while(!dq.empty()){
            arr[i][index++] = dq.front();
            dq.pop_front();
        }
    }
}

void rotation(int arr[][21]) {
    int temp[21][21];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            temp[j][N - 1 - i] = arr[i][j];
    memcpy(arr, temp, sizeof(temp));
}

void DFS(int cnt) {
    if(cnt == 5) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(res < MAP[i][j]) res = MAP[i][j];
            }
        }
        return;
    }

    int temp[21][21];
    for(int i = 0; i < 4; i++) {
        memcpy(temp, MAP, sizeof(MAP)); // origin -> copy
        move(MAP);
        DFS(cnt + 1);
        memcpy(MAP, temp, sizeof(MAP)); // copy -> origin
        rotation(MAP);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> MAP[i][j];
        }
    }

    DFS(0);
    cout << res;

    return 0;
}