백준 12094: 2048(Hard)

문제 주소 : www.acmicpc.net/problem/12094

12094번: 2048 (Hard)

문제 확인

 

2048(easy) 문제와 같은 방식, 최대로 움직일 수 있는 횟수가 10번이다.

완전 탐색으로 구현을 하면 시간초과가 나기 때문에 탐색에서 가지치기를 해 주어야 한다.

 

풀이

 

가지치기 조건

1. 배열 값이 변화가 없는 경우

2. 현재 최대값 이상으로 변화할 수 없는 경우

앞으로 n번 움직일 수 있을 때 매번 합처지는 경우를 생각하면 기대값은 (2^n * 현재값) 으로 볼 수 있다. 현재까지 탐색을 통해 얻어낸 최대값이 이보다 크다면 탐색을 할 필요가 없는 것이다.

 

기대값 계산 시 shift 연산자, 미리 계산해둔 전역변수 사용 등 해 보았지만 그 상황에서 pow 함수를 활용하여 계산하는 것이 가장 좋은 결과를 얻을 수 있었다.

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
int n, result;
 
typedef struct node {
    int ary[20][20];
    node() {};
    void operator=(const node &m) const { memcpy((void*)m.ary, this->ary, sizeof(ary)); }
    bool operator==(const node &m) const {
        for (int i = 0, j = 0; i < n; i++, j = 0) {
            while (j < n)
                if (this->ary[i][j] != m.ary[i][j++]) return false;
        }
        return true;
    }
}node;
 
int move(int d, int A[][20]) {
    int Max_Value = 0;
    if (d == 0) {
        for (int i = 0; i < n; i++) {
            int Value = -1;
            int Idx = n;
 
            for (int j = n - 1; j >= 0; j--) {
                if (A[i][j] == 0) continue;
                if (A[i][j] == Value) {//이전값과 같으면 합침
                    A[i][Idx] <<= 1;
                    Value = -1;
                }
                else {//다르면 이동
                    Value = A[i][j]; Idx--;
                    A[i][Idx] = A[i][j];
                }
                Max_Value = std::max(Max_Value, A[i][Idx]);
            }
            for (int j = Idx - 1; j >= 0; j--) A[i][j] = 0;
        }
    }
    else if (d == 1) {
        for (int i = 0; i < n; i++) {
            int Value = -1;
            int Idx = -1;
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 0) continue;
 
                if (A[i][j] == Value) {
                    A[i][Idx] <<= 1;
                    Value = -1;
                }
                else {
                    Value = A[i][j]; Idx++;
                    A[i][Idx] = A[i][j];
                }
                Max_Value = std::max(Max_Value, A[i][Idx]);
            }
            for (int j = Idx + 1; j < n; j++) A[i][j] = 0;
        }
    }
    else if (d == 2) {
        for (int j = 0; j < n; j++) {
            int Value = -1;
            int Idx = n;
 
            for (int i = n - 1; i >= 0; i--) {
                if (A[i][j] == 0) continue;
 
                if (A[i][j] == Value) {
                    A[Idx][j] <<= 1;
                    Value = -1;
                }
                else {
                    Value = A[i][j]; Idx--;
                    A[Idx][j] = A[i][j];
                }
 
                Max_Value = std::max(Max_Value, A[Idx][j]);
            }
            for (int i = Idx - 1; i >= 0; i--) A[i][j] = 0;
        }
    }
    else if (d == 3) {
        for (int j = 0; j < n; j++) {
            int Value = -1;
            int Idx = -1;
 
            for (int i = 0; i < n; i++) {
                if (A[i][j] == 0) continue;
 
                if (A[i][j] == Value) {
                    A[Idx][j] <<= 1;
                    Value = -1;
                }
                else {
                    Value = A[i][j]; Idx++;
                    A[Idx][j] = A[i][j];
                }
                Max_Value = std::max(Max_Value, A[Idx][j]);
            }
            for (int i = Idx + 1; i < n; i++) A[i][j] = 0;
        }
    }
    return Max_Value;
}
 
 
void dfs(int cur, node nd, int max) {
    if (cur > 9) {
        result = max;
        return;
    }
 
    for (int d = 0; d < 4; d++) {
        node tmp = nd;
        int max_value = move(d, tmp.ary);
        if (tmp == nd) continue;//움직임이 없다면 넘어감
        if (result < max_value * std::pow(2, 9 - cur))//기대값 활용, 계산할 수 있는 최대치보다 현재 최대값이 크다면 넘어감
            dfs(cur + 1, tmp, max_value);
    }
 
}
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    node tmp;
    std::cin >> n;
    for (int i = 0, j = 0; i < n; i++, j = 0)
        while (j < n) {
            std::cin >> tmp.ary[i][j];
            if (tmp.ary[i][j] > result) result = tmp.ary[i][j];
            j++;
        }
 
    dfs(0, tmp, 0);
    std::cout << result;
    return 0;
}