백준 13023 ABCDE (C++)

13023번: ABCDE

문제에 주어진 조건을 만족하면 1, 아니면 0을 출력해주면 되는 문제이다. dfs를 이용해 조건에 해당하는지 확인을 해주었다. 관계를 입력받을 때 벡터를 이용하여 양방향으로 저장을 해주었다. 조건에 해당하는 처음 A를 0부터 n-1까지 대입해보면서 dfs를 돌리면서 depth가 4에 해당하면 조건을 만족한 것이므로 1을 출력해주고, 아니면 0을 출력해주었다.
아이디어가 잘 안떠오른 문제였다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, M, res = 0;
vector<int> v[2000];
bool visit[2000];

void dfs(int start, int depth) {
    if (depth == 4) {
        res = 1;
        return;
    }

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

        if (visit[next]) continue;

        visit[next] = true;
        dfs(v[start][i], depth + 1);
        visit[next] = false;
    }
}

void solution() {
    for (int i = 0; i < N; i++) {
        memset(visit, 0, sizeof(visit));
        visit[i] = true;
        dfs(i, 0);
    }

    cout << res;
}

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

    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);
    }

    solution();

    return 0;
}