[BOJ/백준] 13023 - ABCDE

13023번: ABCDE

---

---

---

• 제목

ABCDE 

---

• 조건

시간 제한 : 2 초

메모리 제한 : 512 MB 

---

• 문제

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

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

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

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

---

• 입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

---

• 출력

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

---

예제 입력 1	예제 출력 1
5 4 0 1 1 2 2 3 3 4	1

---

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
vector<int> node[2000];
int depth[2000] = {1, };
bool visited[2000] = {false, }, check = false;
void DFS(int nd){
    if(depth[nd] >= 5){
        check = true;
        return;
    }
    visited[nd] = true;
    for(int n = 0 ; n < node[nd].size() ; n++){
        if(!visited[node[nd][n]]){
            depth[node[nd][n]] = depth[nd] + 1;
            DFS(node[nd][n]);
            visited[node[nd][n]] = false;
            depth[node[nd][n]] = 1;
        }
    }
    depth[nd] = 1;
    visited[nd] = false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M, node1, node2;
    for(int n = 0 ; n < 2000 ; n++) depth[n] = 1;
    cin >> N >> M;
    for(int n = 0 ; n < M ; n++){
        cin >> node1 >> node2;
        node[node1].push_back(node2);
        node[node2].push_back(node1);
    }
    for(int n = 0 ; n < N ; n++) if(!check) DFS(n);
    cout << check ? 1 : 0 << endl;
    return 0;
}