[C++] 2048 (Easy) (12100번)

2048 (Easy)

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

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

82722

24108

14076

26.262%

문제

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

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

<그림 1>	<그림 2>	<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>	<그림 5>	<그림 6>	<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>	<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다. 

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>	<그림 15>

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

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

 

출력

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

---

문제풀이

브루트 포스로 시간 복잡도가 이게 될까? 라는 의문이 있었다. 최대 5번 이라고 하였으므로 총 분기 되는 경우의 수가 4^5(1024)이다. 1024에 배열의 크기 20*20을 곱해주면 40만 정도가 나오므로 시간 복잡도에서 걸리지 않는다! 그러니까 그냥 맘놓고 완전탐색으로 풀면 된다.

bfs를 사용할까 고민했는데, 이 문제 같은 경우는 각각 숫자를 담은 2차원 배열을 갖고 있어야 한다. 큐에 이 배열을 각각 담아서 돌릴 생각을 하니 용량을 많이 잡아먹을것 같다고 생각해서 dfs를 사용하기로 했다.

 

크게 세 부분으로 나누어 주었다.

1. 모든 경우의 수를 배열로 만들어 준다. [상, 상, 상, 상, 상] ..... [하, 하, 하, 하, 하] 까지 총 1024의 경우의 수만큼 dfs를 통해 배열을 만들어 주었다.

2. 숫자를 이동시키는 함수를 만들었다. 상, 하, 좌, 우로 숫자를 이동시키는 함수를 만들어 주었다.

3. 숫자를 합치는 함수를 만들었다. 이동이후 숫자를 합치고, 다시 이동하는 방식으로 구현하였다. 2번 함수를 회당 두번 쓰는 것이다.

 

다 풀고 다른 사람들을 보니 2,3번을 그냥 합쳐서 구현하면 코드 길이가 훨씬 짧아지고, 배열 탑색횟수도 더 줄어들어 내 풀이가 속도적으로 좋은 풀이는 아니라고 생각했다. 또 2, 3번을 합쳐서 구현하는게 그렇게 길지 않았다. 난 고민하다가 길고 복잡할까봐 분할해서 구현했는데 항상 뭐가 더 이득일지 애매한것 같다. 합치려다 시간이 너무 오래걸린 적도 있기 때문에.. 잘 조절하는게 중요하다.

 

원본 배열을 놔두고, 인자로 전달해주기 위해 2차원 벡터를 사용해 값을 복사하여 구현하였다.

#include <iostream>
#include <vector>

using namespace std;

int n;
int arr[20][20];
int answer;

// 0은 위로, 1은 오른쪽으로, 2는 아래로, 3은 왼쪽으로

void move(int d, vector<vector<int>>& v) {
    if(d == 0) {
        for(int j=0; j<n; j++) {
            int idx = 0;
            for(int i=0; i<n; i++) {
                if(v[i][j] != 0) {
                    int tmp = v[i][j];
                    v[i][j] = 0;
                    v[idx++][j] = tmp;
                }
            }
        }
    }
    else if(d == 1) {
        for(int i=0; i<n; i++) {
            int idx = n-1;
            for(int j=n-1; j>=0; j--) {
                if(v[i][j] != 0) {
                    int tmp = v[i][j];
                    v[i][j] = 0;
                    v[i][idx--] = tmp;
                }
            }
        }
    }
    else if(d == 2) {
        for(int j=0; j<n; j++) {
            int idx = n-1;
            for(int i=n-1; i>=0; i--) {
                if(v[i][j] != 0) {
                    int tmp = v[i][j];
                    v[i][j] = 0;
                    v[idx--][j] = tmp;
                }
            }
        }
    }
    else {
        for(int i=0; i<n; i++) {
            int idx = 0;
            for(int j=0; j<n; j++) {
                if(v[i][j] != 0) {
                    int tmp = v[i][j];
                    v[i][j] = 0;
                    v[i][idx++] = tmp;
                }
            }
        }
    }
}

void merge(int d, vector<vector<int>>& v) {
    if(d == 0) {
        for(int j=0; j<n; j++) {
            for(int i=0; i<n-1; i++) {
                if(v[i][j] != 0 && v[i][j] == v[i+1][j]) {
                    v[i][j] *= 2;
                    v[i+1][j] = 0;
                    i++;
                }
            }
        }
    }
    else if(d == 1) {
        for(int i=0; i<n; i++) {
            for(int j=n-1; j>0; j--) {
                if(v[i][j] != 0 && v[i][j] == v[i][j-1]) {
                    v[i][j] *= 2;
                    v[i][j-1] = 0;
                    j--;
                }
            }
        }
    }
    else if(d == 2) {
        for(int j=0; j<n; j++) {
            for(int i=n-1; i>0; i--) {
                if(v[i][j] != 0 && v[i][j] == v[i-1][j]) {
                    v[i][j] *= 2;
                    v[i-1][j] = 0;
                    i--;
                }
            }
        }
    }
    else {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n-1; j++) {
                if(v[i][j] != 0 && v[i][j] == v[i][j+1]) {
                    v[i][j] *= 2;
                    v[i][j+1] = 0;
                    j++;
                }
            }
        }
    }
}

int findMax(vector<vector<int>>& v) {
    int ret = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            ret = max(ret, v[i][j]);
        }
    }
    return ret;
}

void dfs(vector<int> v) {
    if(v.size() == 5) {
        vector<vector<int>> vv;
        for(int i=0; i<n; i++) {
            vector<int> tmp;
            for(int j=0; j<n; j++) {
                tmp.push_back(arr[i][j]);
            }
            vv.push_back(tmp);
        }

        for(int i=0; i<v.size(); i++) {
            move(v[i], vv);
            merge(v[i], vv);
            move(v[i], vv);
        }
        answer = max(answer, findMax(vv));
        return;
    }

    for(int i=0; i<4; i++) {
        v.push_back(i);
        dfs(v);
        v.pop_back();
    }
}

int main() {
    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> arr[i][j];
        }
    }
    vector<int> v;
    dfs(v);
    cout << answer;
    return 0;
}

 

직관적이긴 하지만, 성능이 좋은 코드는 아니다.