2819. 격자판의 숫자 이어 붙이기 D4

간단한 DFS 문제다

행렬이 컸다면 DFS는 시간 초과가 나겠지만 4*4 행렬이라 DFS로도 충분하다.

4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다.
격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다.
이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다.
단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다.
격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스마다 4개의 줄에 걸쳐서, 각 줄마다 4개의 정수로 격자판의 정보가 주어진다.

[출력]
각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 격자판을 이동하며 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 출력한다.
 

사이즈가 작은 행렬을 DFS 하면 되는 문제라 어렵지는 않았다.

다만 걱정은 bool check[9999999]가 될지.. 이게 가장 의문이었는데 되더라

1. 4*4 입력 받기

2. 랜덤한 위치에서 출발한다 했으므로 모든 점에서 한번씩 DFS

3. 서로 다른 길을 찾기 위해 bool check[9999999]를 사용, 인자는 지금 갔던 길 * 10 + 현재 위치 하면 int 형태로 길 기억 가능

4. 깊이가 7이 되었을 때, check를 검사해 false면 true로 바꾸고 ans++

#include <iostream>
#include <string.h>
 
using namespace std;
int MAP[4][4],ans,moveX[]={-1,0,1,0}, moveY[]={0,1,0,-1};
bool check[9999999];
void solve(int x, int y, int str,int dep)
{
    if (dep == 7)
    {
        if(!check[str])
        {
            ans++;
            check[str]= true;
        }return;
    }
    for(int i=0;i<4;i++)
    {
        int mx = x + moveX[i];
        int my = y + moveY[i];
        if(mx<0||my<0||mx>=4||my>=4) continue;
        solve(mx, my, str*10+MAP[mx][my], dep+1);
    }
}
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    int tc;
    cin>>tc;
    for(int T=1;T<=tc;T++)
    {
        memset(check,false,sizeof(check));
        ans=0;
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
            {
                cin>>MAP[i][j];
            }
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
            {
                solve(i,j,MAP[i][j],1);
            }
        cout<<'#'<<T<<' '<<ans<<'\n';
    }
    return 0;
}