백준 13023 ABCDE

깊이가 5에 도달했을 때(코드 구현 상으로는 4) 1을 출력하고 종료하면 되고 도달하지 못했을 경우 0을 출력하면 되는 문제이다.
모든 경우에 대해 따져봐도 2,000 * 2,000 = 4,000,000 약 4백만밖에 되지 않기 때문에 그냥 하고싶은 대로 하면 된다.

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

int n, m;
vector<vector<int>> graph(2000);
int vis[2000];
void dfs(int k, int now) {
    if (k == 4) {
        cout << 1;
        exit(0);
    }
    for (int i = 0; i < graph[now].size(); ++i) {
        int next = graph[now][i];
        if (vis[next]) continue;
        vis[next] = 1;
        dfs(k+1, next);
        vis[next] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.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) {
        vis[i] = 1;
        dfs(0, i);
        for (int j = 0; j < n; ++j) {
            if (vis[j]) vis[j] = 0;
        }
    }
    cout << 0;
}