[Baekjoon,12100]2048 (Easy)

해결

이 문제는 현재 상태에서 다음 상태로 4개가 만들어지는데 총 5번을 움직인 뒤에 만들어진 상태들 중 제일 큰 원소를 가진 상태의 원소의 값을 출력하면 된다. 즉, 현재 상태에서 기울였을 때 만들어지는 상태를 구현하는 것과 탐색을 통해 5번 기울이기를 했을 때 최대 값을 구하는 것을 구현하면 된다.

무식한 방법

초기에는 기울였을 때 기울인 방향에서 가까운 원소부터 이동을 시작했다. 예를 들어 위로 기울이면 위에서 가장 왼쪽에 있는 원소부터 이동을 시작했다. 위쪽에 숫자가 0일때 계속 이동하다 0이 아니면 이동을 멈추었다. 그 후 숫자가 합쳐질 수 있는 경우 합쳤는데 아래에 조건이 있다.

1. 이동한 숫자와 이동하려는 방향의 한 칸 앞에 있는 숫자가 같다.
2. 범위를 초과하지 않는다.
3. 이전에 이미 합쳐진 숫자이면 안된다.

3번에 대해 생각하지 못하여 디버깅을 한참 하였었다. 만약 아래와 같은 입력인 경우를 생각 해보자.

3
2 0 0
2 0 0
4 0 0

위로 합치는 경우 2와 2가 합쳐져 4가 되는데 이때 다시 4와 4가 합쳐져 8이 되어버린다.

이와 같은 방법으로 아래와 같은 함수를 작성 했으나 계속해서 틀렸습니다.를 받고 있다. 디버깅에 성공했다. 그 이유는 up 함수는 제대로 작성했는데 다른 방향 함수에서 잘못 작성했기 때문이다. down방향을 예로 들면 index접근 순서가 아래쪽 가장 왼편부터 접근했어야 하는데 정신이 다른 곳에 팔렸는 지 엉뚱하게 접근하고 있었다.

void up(vector<vector<int> >& board)
{
    for(int x=0;x<n;++x)
    {
        bool isCombined=false;
        for(int y=1;y<n;++y)
        {
            int ny=y, nx=x;
            // 숫자를 이동할 수 있을 때 까지 한 칸씩 이동한다.
            while(ny>0 && board[ny-1][nx]==0)
            {
                board[ny-1][nx]=board[ny][nx];
                board[ny][nx]=0;
                --ny;
            }
            // 숫자가 합쳐질 수 있는 경우
            if(!isCombined && ny>0 && board[ny][nx]==board[ny-1][nx])
            {
                board[ny-1][nx]=board[ny][nx]*2;
                board[ny][nx]=0;
                isCombined=true;
            }
            else if(board[ny][nx]!=0)
                isCombined=false;
        }
    }
}

결국 디버깅에 실패(이유는 아직 모르겠다..)한 코드를 두고 성공하고 함수를 하나에 통합하는 방법이 있을 것 같아 구글링을 해본 결과 다음과 같은 좋은 아이디어를 얻었다.

새로운 아이디어

숫자가 0인 경우 값들이 기울인 쪽으로 이동하며 이동시 닿는 숫자가 같은 경우 합친다는 생각을 할 수 있다. 그리고 적절히 처리하면 방향마다 코드를 따로 작성하지 않아도 된다. 방향에 따라 다음과 같은 처리를 하면 코드가 굉장히 간결해진다.

• 만약 위, 아래와 같은 방향이면 임시 배열에 세로줄 값들을 넣고, 그 외의 방향에는 가로줄 값들을 넣는다.
  • 이때 숫자가 0인 경우는 넣지 않는다.
• n-1번 인덱스에서 접근을 시작해야 하는 경우(오른쪽, 위) 배열을 뒤집는다.

그 후 새로운 순열에 임시 배열에서 인접한 인덱스에 값이 같다면 2배 값을 새로운 순열에 넣고 그 인접한 값은 건너 뛴다. 이 다음에는 다시 역변환하여 상태 보드에 값을 넣으면 된다. 이 아이디어는 박트리 블로그에서 알게 되었다. 이와 같은 구현은 아래에서 볼 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N=20;

// 0: 좌, 1: 우, 2: 상, 3: 하
enum{ LEFT=0, RIGHT, UP, DOWN };

int board[MAX_N][MAX_N];
int n,ret;

// 배열에서 최대 원소의 값을 반환
int getMaxVar()
{
    int maxNum=0;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            maxNum=max(maxNum,board[i][j]);
    return maxNum;
}

void update(int count)
{
    // 기저 사례
    if(count==5)
    {
        ret=max(ret,getMaxVar());
        return;
    }
    for(int dir=0;dir<4;++dir)
    {
        // 현재 상태의 보드를 저장해 두자
        int original[MAX_N][MAX_N];
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                original[i][j]=board[i][j];
        
        // q번째 행 or 열에 대해 블록을 옮긴다.
        for(int q=0;q<n;++q)
        {
            vector<int> temp;
            for(int p=0;p<n;++p)
                // 방향이 세로이면 행과 열을 뒤집고,
                // 0은 건너 뛰어 저장한다.
                if((dir<2) ? board[q][p] : board[p][q])
                    temp.push_back(dir<2 ? board[q][p] : board[p][q]);
            // 반대쪽에서 역으로 시작(n-1 -> 0)하는 경우 순서를 뒤집는다.
            if(dir==RIGHT || dir==UP)
                reverse(temp.begin(), temp.end());
            
            vector<int> perm;
            for(int p=0;p<temp.size();++p)
                // 다음 블록과 같으면 2배로 늘린다.
                if(p+1<temp.size() && temp[p]==temp[p+1])
                {
                    perm.push_back(temp[p]*2);
                    // 다음 것은 건너 뛴다.
                    ++p;
                }
                else
                    perm.push_back(temp[p]);
            // 남은 공간은 0으로 채운다. 
            for(int p=perm.size();p<n;++p)
                perm.push_back(0);
            
            // 값을 다음 보드에 넣기 위해 재 정렬이 필요한 경우 뒤집는다.
            if(dir==RIGHT || dir==UP)
                reverse(perm.begin(), perm.end());
            for(int p=0;p<n;++p)
                (dir<2 ? board[q][p] : board[p][q])=perm[p];
        }
        update(count+1);
        // 다시 원래 상태로 되돌린다. 
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                board[i][j]=original[i][j];
    }
}

int main()
{
    cin>>n;
    for(int y=0;y<n;++y)
        for(int x=0;x<n;++x)
        {
            cin>>board[y][x];
            ret=max(ret,board[y][x]);
        }
    
    update(0);
    cout<<ret<<endl;
    return 0;
}