[백준 13023, c++] ABCDE

문제 번호

• 13023(https://www.acmicpc.net/problem/13023)

문제 및 입/출력

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

5 4 0 1 1 2 2 3 3 4

예제 출력1

1

예제 입력2

5 5 0 1 1 2 2 3 3 0 1 4

예제 출력2

1

예제 입력3

6 5 0 1 0 2 0 3 0 4 0 5

예제 출력3

0

 

 

예제 입력4

8 8 1 7 3 7 4 7 3 4 4 6 3 5 0 4 2 7

예제 출력4

1

 

문제 풀이

최소 5명, 최대 2000명의 입력된  사람들중에서 A-B, B-C, C-D, D-E와 같은 4쌍의 친구 관계가 성립되면 1을 출력하고 아니면 0을 출력하는 문제이다. vector를 활용하여 친구관계를 나타내었고, dfs를 이용해 탐색을 진행하였다.

모든 사람의 번호에서 각각 탐색을 진행하고, 아직 탐색되지 않은 친구관계를 찾아가면서 진행된다.

 

 

소스 코드

/* https://www.acmicpc.net/problem/13023 */
 
#include <iostream>
#include <cstring>
#include <vector>
 
using namespace std;
 
#define MAX 2000 + 1
 
int n, m;
bool visit[MAX], answer = 0;
vector<int> v[MAX];
 
void dfs(int idx, int cnt) {
    if (cnt == 4) {
        answer = true;
        return;
    }
 
    visit[idx] = true;
    for (int i = 0; i < v[idx].size(); i++) {
        int n_idx = v[idx][i];
        if (visit[n_idx] == false) {
            dfs(n_idx, cnt + 1);
        }
        if (answer == true) return;
    }
    visit[idx] = false;
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    for (int i = 0; i < n; i++) {
        memset(visit, false, sizeof(visit));
        dfs(i, 0);
        if (answer == true) break;
    }
    if (answer == true) cout << 1 << "\n";
    else cout << 0 << "\n";
 
    return 0;
}