BOJ13023 ABCED
문제
BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
- A는 B와 친구다.
- B는 C와 친구다.
- C는 D와 친구다.
- D는 E와 친구다.
- 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.
해설
단순하게 생각해보면
그래프 안에 깊이가 4이상인 트리가 존재하는지 판별하는 문제로 바꿀 수 있다.
접근방식 1 (dfs)
#include <bits/stdc++.h>
using namespace std;
vector<int> a[2001];
bool seen[2001];
void dfs(int i,int d){
if(seen[i])return;
if(d>3){
cout << 1;
exit(0);
}
seen[i]=1;
for(int&v:a[i]){
if(seen[v])continue;
dfs(v,d+1);
}seen[i]=0;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n,m;
cin >> n >> m;
while(m--){
int x,y;
cin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}for(int i=0; i<n; i++){
dfs(i,0);
fill(seen,seen+n,0);
}cout << 0;
}