[백준][12100번][DPS] 2048 (Easy)

스도쿠

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

<문제>

<코드>

#include <bits/stdc++.h>
 
 
using namespace std;
int n;
int mat[20][20];
//idx = 현재 깊이
int solve(int idx)
{
    if(idx==5)
    {
        int ret=0;
        //블록중에 최대 블록을 찾음.
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                ret = max(ret,mat[i][j]);
        }
        return ret;
    }
    int ret=0;
    //상하좌우 4방향에 대해서 0좌1우2상3하
    for(int i=0;i<4;i++)
    {
        // 현재 상태 공간을 저장
        int temp[20][20];
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                temp[j][k]=mat[j][k];
        // q행(또는 열)에 대해서 블록을 저장하고 합침
        for(int q=0;q<n;q++)
        {
            //방향이 세로인 경우 행과 열을 뒤집음
            //방향이 1또는 3인경우 순서를 뒤집음
            vector<int> tmp;
            for(int p=0;p<n;p++)
                //0이 아닌 원소를 tmp 배열에 저장
                if(i<2?mat[q][p]:mat[p][q]!=0)
                    tmp.push_back(i<2?mat[q][p]:mat[p][q]);
            //뒤집기
            if(i==1||i==3)
                reverse(tmp.begin(),tmp.end());
            vector<int> perm;
            for(int p=0;p<tmp.size();p++)
                //다음 것과 비교해서 같은 경우 2배로 늘려서 perm배열에 저장, 다음 원소는 건너 뜀
                if(p+1<tmp.size()&&tmp[p]==tmp[p+1])
                {
                    perm.push_back(tmp[p]*2);
                    p++;
                }
                //아닌 경우 그냥 저장
                else
                    perm.push_back(tmp[p]);
            //빈 공간만큼 0 추가
            for(int p=perm.size();p<n;p++)
                perm.push_back(0);
            //뒤집음
            if(i==1||i==3)
                reverse(perm.begin(),perm.end());
            //다음 상태 공간에 저장
            for(int p=0;p<n;p++)
                (i<2?mat[q][p]:mat[p][q])=perm[p];
 
 
        }
        //다음 상태 공간으로 전이
        ret=max(ret,solve(idx+1));
        //원래 상태 공간 복구
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                mat[j][k] = temp[j][k];
 
    }
    return ret;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&mat[i][j]);
        }
    }
    printf("%d\n",solve(0));
}
 

<문제 푼 요령>

1. 모든 경우를 다 탐색해봐야 하므로 dfs로 접근할 수 있다.

2. 4방향을 전부 일일이 구현하는 것은 실수를 유발할 수 있으므로 왼쪽으로 가는 것 하나만 구현하여 행렬을 바꾸거나 push_back 순서를 바꿈으로서 상하좌우 모두를 구현할 수 있다. 

3. 이동할 때에는 저런식으로 방향을 바꾸어주고 다시 원래대로 해줌으로서 원래 행렬을 나타내준다. 백트래킹을 활용한 것을 볼 수 있다.