BOJ) 2210 - 숫자판 점프

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

2210번: 숫자판 점프

한 정점에서 다른 정점으로 중복 방문이 가능하기에, 인접 정점으로 DFS를 수행하면서 깊이가 6이 될 때의 값을 Set에 저장합니다.

Set은 중복된 값을  허용하지 않기에 Set의 사이즈가 답이 됩니다.

---

C++ 소스 코드

#include <cstdio>
#include <string>
#include <set>
using namespace std;
set<int> st;
int a[5][5];
const int dx[]={0,0,-1,1}, dy[]={-1,1,0,0};
void backtrack(int x, int y, int len, int now){
    if (len == 6){
        st.insert(now);
        return;
    }
    for(int i=0;i<4;i++){
        int nx = x+ dx[i], ny = y+dy[i];
        if (nx <0|| nx>=5 || ny<0 || ny>=5) continue;
        backtrack(nx,ny,len+1,now*10+a[nx][ny]);
    }
}
int main(){
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            scanf("%1d", a[i][j]);
        }
    }
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            backtrack(i,j,1, a[i][j]);
        }
    }
    printf("%d\n",(int)st.size());
    return 0;
}