[algorithm] 백준 - ABCDE

친구 관계가 4 depth로 이루어져있을 경우 1을, 없을 경우 0을 출력한다.
dfs로 4 depth까지 탐색이 완료되면 더이상 탐색을 하지 않는다.

 

반복문을 통해 정점을 탐색하는데
정점을 탐색할 때 어디서 depth가 4가 나올지 모르기 때문에
방문 기록을 탐색 후 초기화한다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> friendVector[2000];
int visited[2000];
int n;
bool isFour = false;
void initVisited(){
    for(int i = 0; i <n; i++){
        visited[i] = false;
    }
}
void dfs(int depth, int y){
    visited[y] = true;
    if(depth == 4){
        cout << 1;
        isFour = true;
        return;
    }
    for(int i = 0; i < friendVector[y].size(); i++){
        if(!visited[friendVector[y][i]])
            dfs(depth + 1, friendVector[y][i]);
    }
    visited[y] = false;
}
int main(void){
    int count;
    cin >> n >> count;
    for(int i = 0; i < count; i++){
        int a, b;
        cin >> a >> b;
        friendVector[a].push_back(b);
        friendVector[b].push_back(a);
    }
    initVisited();
    for(int i = 0; i < n; i++){
        dfs(0, i);
        if(isFour) break;
    }
    if(!isFour) cout << 0;
}

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102808.cpp

jeongdaeun98/algorithm