[Softeer] Lv3.순서대로 방문하기

https://softeer.ai/practice/6246

M 개의 노드가 순서를 맞춰서 제공된다
그 순서에 맞게 방문했을시에 몇번의 전체 방문이 가능한지에 대한 문제이다.

N의 크기를 보면 4이다,,상당히 작아서 조금 쉽게 접근할수가 있었다.

나는 단순하게 생각했다.
A,B,C 의 순서가 주어지면 (A-B, B-C) 가능하면 +=1
그리고 1까지의 가는데 전체의 시간복잡도가 N*2 만 들것이고 시간초과는 안날꺼같았다.

그래서 그냥 한개의 함수 안에 A-B가 충족되면 B-C로 가는 식으로 코드를 짜봤다.

#include <iostream>
#include <vector>

using namespace std;

int N,M;
int answer;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int arr[5][5];
int visited[5][5];
vector<pair<int,int>> v;


void DFS_recur(int cnt,int x,int y,int endX,int endY) {
    
//    cout << x << " " << y << " " << cnt << "\n";
    int dx,dy;
    if(x==endX and y==endY) {
        
//        cout << "# " << x << " " << y << " " << cnt << "\n";
        
        if(cnt==M-2) {
            answer+=1;
        }
        else {
            DFS_recur(cnt+1, v[cnt+1].first, v[cnt+1].second, v[cnt+2].first, v[cnt+2].second);
        }
        return;
    }
    
    for(int i=0;i<4;i++) {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        
        if(dx<=0 or dx>N or dy<=0 or dy>N or visited[dx][dy]==1) {
            continue;
        }
        
        if(arr[dx][dy]==0) {
            visited[dx][dy]=1;
            DFS_recur(cnt,dx, dy, endX, endY);
            visited[dx][dy]=0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> N >> M;
    
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            cin >> arr[i][j];
        }
    }
    
    for(int i=0;i<M;i++) {
        int start,end;
        cin >> start >> end;
        v.push_back({start,end});
    }
    
    visited[v[0].first][v[0].second]=1;
    DFS_recur(0, v[0].first, v[0].second, v[1].first, v[1].second);
    
    cout << answer << "\n";
    
    return 0;
}