2048 (Hard)

백준 12094번: 2048 (Hard)

아이디어

구현 부분과 가지치기 부분으로 나뉜다.

구현

상하좌우로 미는 함수를 모두 구현하면 귀찮다. 한쪽 방향으로 미는 함수만 하나 구현해놓고, 배열을 90도씩 돌려가면서 밀면 모든 방향으로 다 밀 수 있다.
왼쪽으로 미는 기준으로 설명하겠다. 왼쪽으로 밀 때 숫자 사이에 빈 공간(0)이 있는 경우 swap하면서 왼쪽으로 몰아넣는다. 그 이후 두 숫자가 같아서 합쳐질 수 있는 경우를 발견하면 합치고, 다시 빈 공간(0)이 생겼기 때문에 swap하면서 왼쪽으로 몰아넣는다.

가지치기

우선 변화가 없는 경우는 탐색할 필요가 없다. 예를 들어, [[2, 0], [2, 0]] 이 경우 왼쪽으로 밀면 변화가 없다. push함수에서 변화가 일어난 적이 있으면 true를 반환하고, 변화가 일어난 적이 없으면 false를 반환하게 한다. push함수가 false를 반환하면 탐색하지 않고 종료한다.

또 아무리 반복해도 현재 최댓값에 도달할 수 없는 경우는 탐색할 필요가 없다. 예를 들어 현재 최댓값이 1024라 하자. 블록을 밀 수 있는 기회가 2번 남았고, 해당 게임판에서 최댓값이 256이면, 남은 기회를 모두 사용해도 1024보다 커질 수 없다. 이런 경우는 탐색하지 않고 종료한다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, MAX = 0;
int board[20][20];

bool pushleft(int v[][20]) { // left push
    bool changed = false;
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N; j++) {
            if (v[i][j]) {
                int tmpj = j;
                while (tmpj && !v[i][tmpj-1]) {
                    changed = true;
                    swap(v[i][tmpj-1], v[i][tmpj]);
                    tmpj--;
                }
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N-1; j++) {
            // merge
            if (v[i][j] && v[i][j+1] && v[i][j] == v[i][j+1]) {
                changed = true;
                v[i][j] *= 2;
                v[i][j+1] = 0;
                int tmpj = j+1;
                while (tmpj < N-1) {
                    swap(v[i][tmpj], v[i][tmpj+1]);
                    tmpj++;
                }
            }
        }
    }
    return changed;
}

void rotate(int v[][20], int nv[][20]) { // cw
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            nv[j][N-1-i] = v[i][j];
        }
    }
}

void solve(int cnt, int v[][20]) {
    int curmax = 0;
    for (int i = 0; i < N; i++) {
        curmax = max(curmax, *max_element(v[i], v[i]+20));
    }
    if (curmax*(int)pow(2, 10-cnt) <= MAX) {
        return;
    }
    if (cnt == 10) {
        MAX = max(MAX, curmax);
        return;
    }

    int varr[4][20][20] = {};
    rotate(v, varr[0]);
    for (int i = 1; i < 4; i++) {
        rotate(varr[i-1], varr[i]);
    }    
    for (int i = 0; i < 4; i++) {
        if (pushleft(varr[i])) {
            solve(cnt+1, varr[i]);            
        }
    }
}

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 >> board[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        MAX = max(MAX, *max_element(board[i], board[i]+20));
    }
    solve(0, board);
    cout << MAX;

    return 0;
}

여담

이렇게 빡센 구현 문제라니.. index 넘어가지 않게 조심! 문제풀때 발생한 오류의 8할 이상이 index 문제였다.