[12100] 2048 (Easy)

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

2048 이라는 게임이 있다.

난 이 게임을 핸드폰 앱으로 처음 했었는데

상 하 좌 우 움직이면서 같은 숫자들을 합치면서 높은 수를 만들어 내는 게임이다.

이 문제 이름은 2048 (Easy) 이다.

주어진 정보를 이용해 2048 게임을 시뮬레이션 해보는 문제이다.

Easy라는 단어가 들어간 이유는 아마 5번의 횟수제한 때문인 것같다.

친절하게 5번의 횟수를 정해준 이유는 완전탐색을 하라는 뜻으로 받아들이면 된다.

마침 보드의 최대도 20*20 밖에 안된다.

상 하 좌 우를 나타낼 1~4까지의 숫자를 5자리 순열로 만들고 (ex: 11111 11112 11113 .... 44443 44444)

각 순열의 이동이 모두 끝난 후의 보드의 최대 값을 계속 갱신해가며 문제를 풀면 된다.

사실 문제를 푸는 아이디어는 그렇게 어렵지 않다.

이 문제에서 어려운 점은

1. 올바른 순열을 만들어 낼 수 있나

2. 이동을 매끄럽게 진행할 수 있나

이렇게 두 가지가 있다.

순열을 만드는 법은 예전 글에도 있지만

next_permutation을 이용하는 방법과 재귀 함수를 이용하는 방법이 있다.

이번 문제는 재귀 함수를 이용하는 방법을 소개하겠다.

int visit[10];
void func(int num){
    if(num >= 5){
        //여기에 필요한 함수 사용
        //ex)보드 시뮬레이션
        return ;
    }
    for(int i=1; i<=4; i++){
        visit[num] = i;
        func(num + 1);
        visit[num] = 0;
    }
}
int main(){
    func(0);
}

위의 코드가 11111~44444까지의 순열을 만드는 코드이다.

visit이라는 int 배열 안에 순열이 만들어 지는 것이다.

코드의 진행을 조금 설명하자면

먼저 main에서 func(0)이 실행된다. -> num은 0이므로 if문 안에 들어가지 않는다. -> for문을 실행 visit[0]에 1이 들어간다.

-> func(1)이 실행된다. -> num은 1이므로 if문 안에 들어가지 않는다. -> for문을 실행 visit[1]에 1이 들어간다 -> ...

이렇게 하면 가장 먼저 num이 5가 됐을 때 visit배열안엔 11111이 들어가게 된다. 

바로 이때 if문의 조건을 만족하므로 

if문안에 함수 호출이나 해야할 코드를 작성해주면 된다. 이 문제같은 경우는 보드의 움직임을

시뮬레이션하는 코드가 되겠다.

여기서 재귀를 처음 접하면 조금 헷갈릴 수 있는데 이미 visit은 11111인데 

여기서 다른 순열 ex) 22322같은 순열은 어떻게 나올수 있지? 라는 생각이 들수 있다.

먼저, 재귀함수에서는 코드는 순차적으로 진행된다는 사실을 잊어선 안된다.

자 if문안에 보드를 움직이는 함수가 끝났다고 가정하자 그 다음은 어떻게 진행될까?

if문 안에 있는 return으로인해 함수가 종료된다.

그럼 그걸로 모두 끝일까?

아니다. 이건 재귀함수다. 다음 시작점은 func(num+1)의 아랫줄인 visit[num] = 0 이다.

num이 4인 상태이기 때문에 visit은 11110이 된다.

그후 for문의 i가 2가되어 visit은 11112가 되고 다시 func(num+1)로 새로운 func이 호출되고

if문의 조건을 만족해 다시 보드 시뮬레이션 진행하는 것이다.

만약 스택의 개념을 알고있다면 재귀함수 = 스택이라고 생각하면 된다.

위의 원리를 이용해 단지 5칸의 배열로 순열을 사용할 수 있다.

다음 문제는 이동을 매끄럽게 할 수 있느냐이다.

이 문제의 핵심이 되겠다.

나는 각 칸을 진행 방향대로 이동할 수 있는 곳 까지 가보고

그 위치보다 진행 방향으로 한칸 앞에 있는 블럭이 나와 같은 숫자이면 숫자를 2배 곱해주고

처음 위치는 0으로 바꿔준다.

만약 그 블럭이 나랑 다른 숫자이면 현재 위치와 처음 위치의 자리를 바꿔주었다.

위치를 바꾼 이유는 블럭 값이 0 인 곳만 이동 할 수 있으므로

현재 위치가 0 이거나 아니면 이동하지 않는 처음 위치 이기 때문이다.

물론 이 것도 경우를 나누어서 이동하지 않았으면 위치를 바꾸지 않게해도 상관 없지만

귀찮아서 그냥 두 경우 모두 바꿔주는 걸로 했다.

아 그리고 각 블럭은 한 이동에 한 번만 합쳐지므로 check배열을 만들어

현재 블럭이 이미 합쳐진 적이 있는지 없는지 확인해야 한다.

예를 들어 2 2 4 4 를 왼쪽으로 이동시키면 4 8 0 0이 되어야 맞는데

앞의 2 2 가 먼저 4가 되고 3번째 칸의 4와 합쳐져 8 4 0 0이 되면 틀리기 때문이다.

까다로운 점은 처음 시작점과 다음 위치 확인 등인데

이런 것들은 직접 손으로 그려가면서 해야 더 빠르고 정확하게 풀 수 있다.

끝.

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n, maxi;
int borad[22][22], temp[22][22];
int visit[10];
bool check[22][22];
 
int start(){
    for(int k=1; k<=5; k++){
        memset(check, 0, sizeof(check));
        int c = visit[k];
        if(c == 1){ // 좌
            for(int i=0; i<n; i++){
                for(int j=1; j<n; j++){
                    if(!temp[i][j]) continue;
                    int cj = j;
                    while(cj-1 >= 0 && temp[i][cj-1] == 0) cj--;
                    if(cj-1>=0 && temp[i][cj-1] == temp[i][j] && !check[i][cj-1]){
                        check[i][cj-1] = 1;
                        temp[i][cj-1] *= 2;
                        temp[i][j] = 0;
                    }
                    else {
                        int t = temp[i][j];
                        temp[i][j] = temp[i][cj];
                        temp[i][cj] = t;
                    }
                }
            }
        }else if (c == 2){ // 우
            for(int i=0; i<n; i++){
                for(int j=n-2; j>=0; j--){
                    if(!temp[i][j]) continue;
                    int cj = j;
                    while(cj+1 < n && temp[i][cj+1] == 0) cj++;
                    if(cj+1 < n && temp[i][cj+1] == temp[i][j] && !check[i][cj+1]){
                        check[i][cj+1] = 1;
                        temp[i][cj+1] *= 2;
                        temp[i][j] = 0;
                    }
                    else {
                        int t = temp[i][j];
                        temp[i][j] = temp[i][cj];
                        temp[i][cj] = t;
                    }
                }
            }
        }else if(c == 3){ // 상
            for(int j=0; j<n; j++){
                for(int i=1; i<n; i++){
                    if(!temp[i][j]) continue;
                    int ci = i;
                    while(ci-1 >= 0 && temp[ci-1][j] == 0) ci--;
                    if(ci-1 >= 0 && temp[ci-1][j] == temp[i][j] && !check[ci-1][j]){
                        check[ci-1][j] = 1;
                        temp[ci-1][j] *= 2;
                        temp[i][j] = 0;
                    }
                    else {
                        int t = temp[i][j];
                        temp[i][j] = temp[ci][j];
                        temp[ci][j] = t;
                    }
                }
            }
        }else if( c == 4){ // 하
            for(int j=0; j<n; j++){
                for(int i=n-2; i>=0; i--){
                    if(!temp[i][j]) continue;
                    int ci = i;
                    while(ci+1 < n && temp[ci+1][j] == 0) ci++;
                    if(ci+1 < n && temp[ci+1][j] == temp[i][j] && !check[ci+1][j]){
                        check[ci+1][j] = 1;
                        temp[ci+1][j] *= 2;
                        temp[i][j] = 0;
                    }
                    else {
                        int t = temp[i][j];
                        temp[i][j] = temp[ci][j];
                        temp[ci][j] = t;
                    }
                }
            }
        }
    }
    int innerMax = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(innerMax < temp[i][j]){
                innerMax = temp[i][j];
            }
        }
    }
    return innerMax;
}
 
void func(int num){
    if(num > 5){
        memcpy(temp, borad, sizeof(borad));
        maxi = max(start(), maxi);
        return ;
    }
    for(int i=1; i<=4; i++){
        visit[num] = i;
        func(num + 1);
        visit[num] = 0;
    }
}
 
int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &borad[i][j]);
        }
    }
 
    maxi = 0;
    func(1);
 
    printf("%d\n", maxi);
 
    return 0;
}