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

DFS로 4방향 탐색을 통해 모든 경우의수를 다 계산한다.

중복되는 탐색이 많기 때문에, DP로도 가능할 것 같다.

#include <stdio.h>
char check[10000000];
int map[4][4];
void dfs(int i, int j, int number, int depth) {
    if (depth == 7) {
        check[number] = 1;
        return;
    }
    number = number * 10;
    number = number + map[i][j];
    //좌
    if (j - 1 >= 0) {
        dfs(i, j - 1, number, depth + 1);
    }
    if (j + 1 < 4) {
        dfs(i, j + 1, number, depth + 1);
    }
    if (i - 1 >= 0) {
        dfs(i - 1, j, number, depth + 1);
    }
    if (i + 1 < 4) {
        dfs(i + 1, j, number, depth + 1);
    }
}
int main() {
    int T;
    scanf("%d\n", &T);
    for (int testcase = 1; testcase <= T; ++testcase) {
        
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                scanf("%d", &map[i][j]);
        for (int i = 0; i < 10000000; i++)
            check[i] = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                dfs(i, j, 0, 0);
            }
        }
        int cnt = 0;
        for(int i=0;i<10000000;i++){
            if (check[i] != 0)
                cnt++;
        }
        printf("#%d %d\n", testcase, cnt);
    }
    return 0;
}