기존 시도

문제점

다시 시도했는데 틀렸다.
여러 원소를 다양한 각도에서 접근하면서 사이클도 막아야하는데, 방문 배열 전체를 초기화하는 방법밖에 생각이 나지 않았다.

첫 번째 시도

그래서 그냥 돌린 첫번째 결과 실패. 시간 초과는 아니었지만 당연히 커버되지 않는 케이스가 있다.

두 번째 시도

두 번째 시도에서 재귀를 빠져 나올 때 방문을 취소했다.
목적이 끝났기 때문이다. 백트래킹의 느낌을 주었다.
결과는 성공이다.

코드

// 2022.01.03 10:26:18
// 13023_2 https://boj.kr/13023_2
#include <bits/stdc++.h>
using namespace std;
int n, m;

vector<vector<int>> rel(2001, vector<int>());
bool visited[2001];
bool dfs(int cur, int depth)
{
    if (depth == 4)
        return true;
    visited[cur] = true;

    for (int &next : rel[cur])
    {
        if (!visited[next] && dfs(next, depth + 1))
            return true;
    }
    visited[cur] = false;
    return false;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        rel[a].push_back(b);
        rel[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!visited[i] && dfs(i, 0)){
            cout << 1;
            return 0;
        }
    }
    cout << 0;
}