BFS/ DFS - 백준 13023 ABCDE C++

1. 문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

2.  입력

5 4 

/*첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.*/

 

0 1  

1 2

2 3

3 4

/* 둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며,

   a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b)

   같은 친구 관계가 두 번 이상 주어지는 경우는 없다  */

3.  출력 

1

/*문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.*/

4.  답안

#include <iostream>
#include <vector>
using namespace std;
 
 
 
int n,m;
bool visited [2001] = {false, } ; // false로 초기화 
vector <int> graph[2001]; 
 
/* 배열보다 성능이 좋기 때문에 
그래프를 벡터로 구현한다. */
 
int friends= 0; 
 
/* 친구 관계에 포함되는 친구수 
   friends가 5가 되면 조건에 충족하게 된다 . */
 
void dfs (int start ){ // dfs 함수 
 
    visited[start] = true; // 시작 정점 방문 표시
    friends ++;  //   
 
    if (friends == 5 ){ // 조건을 만족하면 
         cout << 1 ;  // 찾고자 하는 조건을 만족했음을 표시 
         exit(0);  // 프로그램 종료
    }
 
    for (int i = 0 ; i < graph[start].size() ; i ++){
        int node = graph[start][i]; // start와 연결된 node
        if(!visited[node]){//해당 노드를 아직 방문하지 않았다면 
            dfs(node); // 재귀함수
        }
    }
 
    visited[start] = false; // 시작 정점 방문 표시 해제
    friends --; 
    return ;
}
 
int main(){ 
 
    cin >> n >> m ; // n과 m 입력 
 
    for(int i = 1 ; i <= m ; i++){
        int a, b; 
        cin >> a >> b ;
        graph[a].push_back(b);
        graph[b].push_back(a);
    } // 그래프 입력 받기 
 
    for (int i = 0 ; i < n ; i ++ ){
        // 시작점을 다르게 하면서 dfs 탐색 
        dfs(i);
    }
 
   
    cout << 0; // abcde를 찾지 못하면 0 출력 
    return 0 ; 
}