백준 2210번 : 숫자판 점프

문제 링크 :https://www.acmicpc.net/problem/2210

2210번: 숫자판 점프

 

 

 문제 설명 

 

처음에 5 x 5 크기의 숫자판이 주어지고 숫자판에서는 상하 좌우 네방향으로 움직일수 있다.

총 6번을 움직일때 얻을수있는 서로 다른 수열 의 갯수 를 출력.

똑같은곳을 여러번 방문 해도된다 .

 

 알고리즘 

 

재귀로 구현.

1. 배열의 (0,0) 부터 (4,4) 까지 다 탐색.

2. dfs 깊이 6일때 check() 함수 

3. check함수는 ans 벡터를 만들고 ans 벡터안에 똑같은 수열이 있는지 판별후 없으면 push_back .

4. ans의 크기 출력.

 

 

 코드 

 

#include<iostream>
#include<vector>
using namespace std;
 
 
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int arr[5][5];
vector<vector<int>> ans;
 
bool check(vector<int> v) {
    int Size = ans.size();
    for(int i = 0; i < Size; i++) {
        if (ans[i] == v)return false;
    }
    return true;
}
 
 
void func(int y,int x,vector<int> v) {
    v.push_back(arr[y][x]);
    if (v.size() == 6) {
        if (check(v))
            ans.push_back(v);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int next_y = y + dy[i];
        int next_x = x + dx[i];
        if (next_x >= 0 && next_x < 5 && next_y >= 0 && next_y < 5) {
            func(next_y, next_x, v);
        }
    }
 
}
 
int main() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> arr[i][j];
        }
    }
    vector<int> a;
    
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            func(i, j, a);
        }
    }
    cout << ans.size();
}