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

• 문제 설명

5×5 크기의 숫자판의 각각의 칸에는 0부터 9까지의 숫자가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다. 숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구해야 한다.

• 문제 풀이

이 또한 DFS로 문제를 해결했는데, 숫자판이 주어졌으므로 좌표로 생각해서 푼다. dx와 dy 배열을 만들어 이동하는 느낌으로 문제를 풀어주면 된다. 문제에서 5X5의 숫자판이 주어졌으므로, for문을 통해 5번이 돌만큼 구성해주어 푼다.

• 정답 코드

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
using namespace std;

vector<vector<int>> board(5, vector<int>(5,0));
int answer = 0;
bool visited[10101010];

int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

void dfs(int x, int y, int sum, int cnt){
    if(cnt == 5){
        if(!visited[sum]){
            visited[sum] = true;
            answer++;
        }
        return;
    }

    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

       if(nx >= 0 && nx < 5 && ny >= 0 && ny < 5){
            dfs(nx, ny, sum*10 + board[nx][ny], cnt+1);
        }
    }    
}

int main() {
    FASTIO;

    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            cin >> board[i][j];
        }
    }

    for(int i = 0; i < 5; i++){
        for(int j = 0;  j < 5; j++){
            dfs(i, j, board[i][j], 0);
        }
    }

    cout << answer << '\\n';

    return 0;
}