백준[2668] - 숫자고르기

문제

백준 2668 문제 보기

접근 방법

문제에서 요구하는 조건을 만족하려면 주어진 숫자들이 사이클을 이루는지 확인하고 사이클 갯수를 출력하면 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>

using namespace std;

int N;
int arr[101];
int visited[101];
vector<pair<int, int>> temp_arr;
set s_idx;

void dfs(int idx) {
    // 다음 방문할 곳
    int next = arr[idx];
    // 방문했다면 사이클이 존재
    if(visited[next] == 1) {
        // 사이클이 존재하는 idx만 따로 저장
        for(int i = next; visited[i] != -1; i = arr[i]) {
            temp_arr.push_back({idx, i});
            idx = i;
            visited[i] = -1;
        }
        return;
    }
    else if(visited[next] == -1 || visited[next] == 0) {
        visited[next] = 1;
        dfs(next);
        visited[next] = -1;
    }
}

int main() {
    cin >> N;
    // 1 ~ N까지 숫자
    for(int i = 1; i <= N; i ++) {
        // i는 1부터 시작
        cin >> arr[i];
    }

    for(int i = 1; i <= N; i ++) {
        temp_arr.clear();
        // 방문 체크
        visited[i] = 1;

        // 사이클 확인
        dfs(i);

        visited[i] = -1;
        // 중복 제거
        for(int t = 0; t < temp_arr.size(); t ++) {
            s_idx.insert(temp_arr[t].first);
        }
    }

    cout << s_idx.size() << endl;
    for (auto s1 = s_idx.begin(); s1 != s_idx.end(); s1++) {
        cout << *s1 << endl;
    }
    return 0;
}