[백준 12100] 2048(Easy)

오랜만에 PS 카테고리에 글을 쓰게 되는것 같습니다.

PS 글을 쓰면 이 글을 보는 사람을 생각하면서 글을 쓰다보니 정작 문제를 푸는 것보다 오래걸려서 잘 안쓰게 되는것 같습니다. 

 

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

12100번: 2048 (Easy)

백준 12100번 2048(Easy)입니다.

삼성 기출로 분류되어있는 문제입니다.

 

핸드폰 게임에도 같은 게임으로 알고 있고 아마 모두들 한번쯤은 이 게임을 실제 경험해본 적이 있을겁니다.

실제 게임에서는 모든 수를 합치는 것이 목적입니다.

 

하지만 이 문제는 요구하는 바가 다릅니다.

그저 5번을 진행 했을 때 가장 큰 수를 만들 수 있는 경우에서의 해당 수를 구하면 됩니다.

 

이동할 수 있는 방법은 4가지입니다. (위,아래,왼쪽,오른쪽)으로 모든 타일을 옮기면 됩니다.

즉 이 4번의 경우를 모두 5번씩 해봐서 가장 큰 수가 나온걸 출력하는 완전탐색입니다.

4가지 경우를 5번씩 다 해보니 시간복잡도는 4^5이 나올겁니다.

 

그리고 해당 타일들이 옮겨지면서 합쳐지는걸 구현해야하니 시뮬레이션 유형에도 포함됩니다.

 

저의 아이디어는 모든 경우를 완전 탐색하는걸 DFS로 구현합니다.

그리고 DFS를 돌릴 위,아래,왼쪽,오른쪽을 옮기는 방법입니다.

특정방향으로 옮길 때 먼저 특정방향에서 0이 아닌 타일이 있는 곳을 find_idx함수를 통해 탐색합니다. 0이 아닌 타일이 없으면 가장 마지막의 위치가 반환됩니다.

 

그리고 해당 위치가 자신과 같은 숫자라면 합쳐지고 합쳐졌다는 표시를 해줍니다.

자신과 다른 숫자라면 해당 칸의 전칸에 현재의 타일을 넣어줍니다.

해당 위치가 빈칸이라면 해당 칸에 현재 타일을 그대로 넣어줍니다.

 

이 방식을 그저 모든 방향에 걸쳐서 해주면 됩니다.

시뮬레이션은 말을 하는 것보다는 역시 백문이 불여일견 코드를 보는게 가장 좋겟죠.

 

#include<iostream>
#include<math.h>
#include<algorithm>
#include<memory.h>
#include<string>
#define endl "\n"
using namespace std;
int N,mat[22][22],check[22][22],dy[4]={-1,0,1,0},dx[4]={0,1,0,-1},mx=-1;
void find_max()
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            mx = max(mat[i][j],mx);
        }
    }
}

int find_idx(int y, int x, int d)
{//0이 아닌 곳을 찾는 함수입니다.
    int ret;
    switch(d)
    {
        case(0):
            ret=y-1;
            for(int i=y-1;i>=0;i--)
            {
                ret = i;
                if(mat[i][x]) break;//자신의 위치부터 탐색하다가 0이 아닌곳이 발견되면 혹은 끝이면 더이상 못가므로 그만합니다.
            }
            return ret; //0이 아닌곳 혹은 더이상 못간곳의 위치가 반환됩니다.
        case(1):
            ret=x+1;
            for(int i=x+1;i<N;i++)
            {
                ret = i;
                if(mat[y][i]) break;
            }
            return ret;
        case(2):
            ret=y+1;
            for(int i=y+1;i<N;i++)
            {
                ret = i;
                if(mat[i][x]) break;
            }
            return ret;
        case(3):
            ret=x-1;
            for(int i=x-1;i>=0;i--)
            {
                ret = i;
                if(mat[y][i]) break;
            }
            return ret;
        default:
            cout << "wrong"<<endl;
            return -1;
    }
}
void lft()
{
    for(int i=0;i<N;i++)
    {
        for(int j=1;j<N;j++)
        {
            if(!mat[i][j]) continue;

            int idx=find_idx(i,j,3);//처음 0이 아닌곳을 찾습니다.
            if(mat[i][idx])//0이 아닌곳이 맞을 때
            {
                if(mat[i][j]==mat[i][idx]&&!check[i][idx]) //자신과 같고 해당 횟수에서 합쳐진 전적이 없는 타일이면 합쳐줍니다
                {
                    mat[i][j]=0; mat[i][idx] *=2; check[i][idx]=1; 
                }
                else//자신과 다르거나 합쳐진 전적이 있으면 해당 인덱스의 전 위치에 넣어줍니다.
                {
                    int tmp=mat[i][j];
                    mat[i][j]=0; mat[i][idx+1]=tmp;
                }
                
            }
            else // 0이면 해당 위치에 넣습니다.
            {
                int tmp=mat[i][j];
                mat[i][j]=0; mat[i][idx]=tmp;
            }
        }
    }
}

void rght()
{
    for(int i=0;i<N;i++)
    {
        for(int j=N-2;j>=0;j--)
        {
            if(!mat[i][j]) continue;

            int idx=find_idx(i,j,1);
            if(mat[i][idx])
            {
                if(mat[i][j]==mat[i][idx] && !check[i][idx])
                {
                    mat[i][j]=0; mat[i][idx] *=2; check[i][idx]=1; 
                }
                else
                {
                    int tmp=mat[i][j];
                    mat[i][j]=0; mat[i][idx-1]=tmp;
                }
            }
            else
            {
                int tmp=mat[i][j];
                mat[i][j]=0; mat[i][idx]=tmp;
            }
        }
    }
}
void go_up()
{
    for(int i=0;i<N;i++)
    {
        for(int j=1;j<N;j++)
        {
            if(!mat[j][i]) continue;

            int idx=find_idx(j,i,0);
            if(mat[idx][i])
            {
                if(mat[j][i]==mat[idx][i]&&!check[idx][i])
                {
                    mat[j][i]=0; mat[idx][i] *=2; check[idx][i]=1;
                }
                else
                {
                    int tmp=mat[j][i];
                    mat[j][i]=0; mat[idx+1][i]=tmp;
                }   
            }
            else
            {
                int tmp=mat[j][i];
                mat[j][i]=0; mat[idx][i]=tmp;
            }
        }
    }
}
void go_down()
{
    for(int i=0;i<N;i++)
    {
        for(int j=N-2;j>=0;j--)
        {
            if(!mat[j][i]) continue;

            int idx=find_idx(j,i,2);
            if(mat[idx][i])
            {
                if(mat[j][i]==mat[idx][i]&&!check[idx][i])
                {
                    mat[j][i]=0; mat[idx][i] *=2; check[idx][i]=1;
                }
                else
                {
                    int tmp=mat[j][i];
                    mat[j][i]=0; mat[idx-1][i]=tmp;
                } 
            }
            else
            {
                int tmp=mat[j][i];
                mat[j][i]=0; mat[idx][i]=tmp;
            }
        }
    }
}
void DFS(int cnt)
{
    if(cnt==5) //현재 몇번 이동했는지 횟수 5번이면 조건 만족으로 그만합니다.
    {
        find_max();//해당 타일중 가장 큰 수를 찾습니다.
        return;
    }
    int cpy[22][22];

    memcpy(cpy,mat,sizeof(mat));
    memset(check,0,sizeof(check));

    lft();//왼쪽으로 옮기고
    DFS(cnt+1);//다음 옮길 행동을 하러 재귀를 들어갑니다.
    memcpy(mat,cpy,sizeof(cpy)); memset(check,0,sizeof(check)); // 재귀를 갔다 왔으면 다시 원상복구 해놓습니다.
    //이를 모든 방향에 맞게 진행합니다.

    rght();
    DFS(cnt+1); 
    memcpy(mat,cpy,sizeof(cpy)); memset(check,0,sizeof(check));
    
    go_up();
    DFS(cnt+1); 
    memcpy(mat,cpy,sizeof(cpy)); memset(check,0,sizeof(check));
    
    go_down();
    DFS(cnt+1);
    memcpy(mat,cpy,sizeof(cpy)); memset(check,0,sizeof(check));

}
int main()
{
    cin >> N;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            cin >> mat[i][j];
        }
    }
    DFS(0);
    cout << mx;
}

 

적고보니 굳이 길게 적은 코드가 몇개 보입니다. 클린코드를 위해 더욱 노력해야겠습니다. 

 

제가 글을 적는 이유는 오답노트의 느낌으로 하고있는데 시뮬레이션 문제는 그냥 구현만 하면 되다보니 그닥 생각할 게 없어서 적을 맛이 안나는군요...해당 유형은 잘 안적게 될 것 같습니다.