[백준/C++] 13023번_ABCDE

문제는 다음과 같습니다.

전형적인 그래프 문제이고,
친구 관계를 잘 보면, "dfs의 깊이가 4이상인 관계가 존재하느냐" 가 문제에서 물어본 핵심입니다.

먼저 저는, 그래프의 관계를 표현하기 위해 벡터 인접리스트를 이용하였습니다. -> vector v[2001];
(이 문제에서는 굳이 인접행렬을 이용하지 않아도 됩니다)

그리고 정의한 DFS는 다음과 같습니다.
DFS의 탈출 조건은, 친구의 연관관계가 4이상 성립할 때입니다.
저는 DFS 함수의 두 번째 인자로, 친구의 명수를 넘겨서 해당 친구가 5번째일때(=관계는 4)를 탈출 조건으로 잡았습니다.

해당 DFS의 함수는 다음과 같습니다.

void DFS(int k, int cnt){
  if(cnt==5){
    state=1;
    return;
  }
  else{
    for(int i=0; i<v[k].size(); i++){
      if(ch[v[k][i]]==0){
        ch[v[k][i]]=1;
        DFS(v[k][i], cnt+1);
        ch[v[k][i]]=0;
      }
    }
  }
}

전체 함수는 다음과 같습니다.

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

int n, m, state=0;
vector<int> v[2001];
int ch[2001]={0, };

void DFS(int k, int cnt){
  if(cnt==5){
    state=1;
    return;
  }
  else{
    for(int i=0; i<v[k].size(); i++){
      if(ch[v[k][i]]==0){
        ch[v[k][i]]=1;
        DFS(v[k][i], cnt+1);
        ch[v[k][i]]=0;
      }
    }
  }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i=0; i<m; i++){
      int a, b; cin>>a>>b;
      v[a].emplace_back(b); v[b].emplace_back(a);
    }

    for(int i=0; i<n; i++){
      ch[i]=1;
      DFS(i, 1);
      ch[i]=0;
      if(state) break;
    }

    cout<<state<<"\n";
    return 0;
}  

2월 16일 복습)

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

 vector<int> v[2001];
 int ch[2001]={0, };
 int n, m, state=1;

 void DFS(int k, int cnt){
   if(cnt==5){
     state=0;
     return;
   }
   for(int i=0; i<v[k].size(); i++){
     if(ch[v[k][i]]==0){
       ch[v[k][i]]=1;
       DFS(v[k][i], cnt+1);
       ch[v[k][i]]=0;
     }
   }
 }

 int main() {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);

     cin>>n>>m;
     for(int i=0; i<m; i++){
       int t1, t2; cin>>t1>>t2;
       v[t1].emplace_back(t2); v[t2].emplace_back(t1);
     }

     for(int i=0; i<n; i++){
       ch[i]=1;
       DFS(i, 1);
       ch[i]=0;
       if(!state) break;
     }
     if(!state) cout<<"1"<<"\n";
     if(state) cout<<"0"<<"\n";
     return 0;
 }