Solution (시간초과)

• 백트래킹을 사용하여 배열에 들어있는 값들을 비교하여 해결하려고 하였다. dfs자체로는 시간초과가 나지 않으나, 비교하는 과정에서 O(N)이 추가되기에 worst case에서 총 O(N^3)의 시간복잡도가 발생하여 시간초과가 발생하였다.

Solution (정답)

• 이를 해결하기 위해서 dfs를 사용한 사이클 탐색 방법을 떠올렸다.
• 만약 방문을 했고, 현재 값과 시작 값이 같다면 해당 값은 포함될 수 있다고 체크해 주었다.

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
#include <string>
#include <stack>
#include <list>
#include <unordered_set>
#include <sstream>
#include <deque>
#include <math.h>
#include <map>
#include <set>

using namespace std;

int N;
int arr[101];
int visited[101];
int answer = 0;
int a_vec[101];

void dfs(int start, int depth){
    if(visited[start]){
        if(start == depth){
            a_vec[answer++] = depth;
        }
    }
    else{
        visited[start] = 1;
        dfs(arr[start], depth);
    }
}

void Solution()
{
    for(int i =1; i<=N; i++){
        for(int j =1; j<=N; j++){
            visited[j]  =0;
        }
        dfs(i, i);
    }
    
    cout << answer << '\n';
    for(int i = 0 ; i<answer; i++){
        cout << a_vec[i] << '\n';
    }   
}

void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
}

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

    Input();
    Solution();
}