[백준/c++] 13023번: ABCDE

 

https://www.acmicpc.net/problem/13023

13023번: ABCDE

 

A-B-C-D-E 이렇게 친구가 되면 친구관계가 존재하는 것인데, 즉 그래프 속 시작점에서부터 쭉 4개의 정점이 있으면 된다.

깊이 우선 탐색인 DFS를 사용하면 된다.

 

만약 A에 연결된 것이 B, C라면 B로 먼저 들어가서 쭉 갔다가 C에 들어가서 쭉 가려면 DFS 내에서 B로 갔던 것(visit)을 취소해야 한다.

그래야 C로 가는 길에 B를 만나도 중복처리를 하지 않기 때문이다.

그러므로 꼭 visit [x] = false를 해줘야 한다.

 

그리고 시작점이 0~n-1 모두 해당되기 때문에 꼭 visit을 초기화를 해줘야 한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
bool ans = false;
vector<int> graph[2001];

void DFS(int x, int cnt, vector<bool> &visit){
    visit[x] = true;
    if(cnt == 4){
        ans = true;
        return;
    }
    
    for(int i=0; i<graph[x].size(); i++){
        int y = graph[x][i];
        if(!visit[y]) DFS(y, cnt+1, visit);
    }
    visit[x] = false;
    return;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=0; 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++){
        vector<bool> visit(n);
        DFS(i, 0, visit);
        if(ans){
            cout << "1\n";
            return 0;
        }
    }
    cout << "0\n";
    return 0;
}