[틀림] 백준 13023 ABCDE // vis 초기화(백트래킹) 필요한 이유

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

* 백트래킹 복습

• depth가 5이상인지 검사
• 이때, vis=0으로 백트래킹 필요

• 즉, 원복시키면서 완탐을 하려고 원상복귀를  하는것이다.
• 완탐을하려면 원복이 필요!

 

 

* 풀이

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

int n,m,ret;
int vis[2004];
vector<int> adj[2004];

int dfs(int cur, int depth) {
   
   if(depth==5) {
      cout<<1;
      exit(0);
   }

   vis[cur]=1;
   int ret = 1;
   for(auto nxt : adj[cur]) {
      if(vis[nxt]) continue;
      ret+=dfs(nxt,depth+1);
   }
   vis[cur]=0; // 탐색후 풀어줘야함!
   return ret;
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   cin>>n>>m;

   for(int i=0;i<m;++i) {
      int a,b;
      cin>>a>>b;
      adj[a].push_back(b);
      adj[b].push_back(a); //a와 b가 친구 -> 양방향맞음
   }

   for(int i=0;i<n;++i) {
      memset(vis,0,sizeof(vis));
      dfs(i,1);
      // if(vis[i]) continue;
      
      // if(dfs(i)>=5) {
      //    cout<<1;
      //    exit(0);
      // }
   }
   // dfs(0);
   // for(int i=0;i<n;++i) {
   //    if(!vis[i]) {
   //       cout<<0;
   //       exit(0);
   //    }
   // }

   cout<<0;
   
   return 0;
}