[13023] ABCDE (C++)

#include <iostream>
#include <vector>

using namespace std;
bool exist = false;

void DFS(int start, vector<vector<int>> &A, vector<bool>& visit, int reps) {
    if (reps == 4) {
        exist = true;
        return;
    }

    for (int i = 0; i < A[start].size(); i++) {
        int next = A[start][i];

        if (visit[next]) continue;
        visit[next] = 1;
        DFS(next, A, visit, reps + 1);
        visit[next] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);

    int n, m; cin >> n >> m;
    vector<vector<int>> A(n);

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        A[u].push_back(v);
        A[v].push_back(u);
    }

    for (int i = 0; i < n; ++i) {
        vector<bool> visit(n);
        visit[i] = 1;
        DFS(i, A, visit, 0);
        if (exist) break;
    }

    cout << exist;

    return 0;
}

 

1. vector를 생성해 친구 관계인 둘 사이에 간선을 생성

2. 초기 노드를 0 놓고 방문 여부를 판별할 bool vector visit, 친구 관계의 수를 카운팅할 reps를 생성

3. DFS 함수를 재귀 함수로 사용하여 visit을 카운팅하며 반복

4. 문제에서 요구하는 친구 관계가 존재하는지를 판별할 bool exist는 reps가 4가 되면 true가 된다

5. 재귀 함수 종료 후 exist 여부를 출력

 

 

reps 범위를 잘못 잡는 등 실수가 많았던 문제