[BOJ] ABCDE 13023번 C++

 

 

문제

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을 출력한다.

 

 

접근 방식

 

생각보다 풀이법은 간단하다.

A,B,C,D,E가 친구임은 즉 4번의 깊이를 가지는 서브트리가 있는지 여부를 확인하는 것이다.

즉, 너비우선탐색으로 각 노드에서 4번의 깊이를 갖는 경로가 있는지 확인하면 된다.!!

 

이때, 방문 배열을 갖고 노드를 방문했는지 확인할 때, 다른 경로로도 확인할 수 있으므로 꼭 방문 해제를 같이 해줘야 한다!!

 

 

코드

 

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

vector<vector<int>> v;
int visited[2002];

bool dfs(int cur, int depth) {
    if(depth == 4) return true; 

    for(auto nxt : v[cur]) {
        if(!visited[nxt]) {
            visited[nxt] = true;
            if(dfs(nxt, depth+1)) return true;
            visited[nxt] = false;
        }
    }
    return false;
}

int main(){
    int N,M; cin>>N>>M;
    v.resize(N);
    
    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++) {
        fill(visited, visited+N, false);
        visited[i] = true;
        if(dfs(i,0)) {
            cout<<1;
            return 0;
        }
        
    }
    cout<<0;
}