백준 2668 숫자고르기 (C++)

2668번: 숫자고르기

dfs를 이용한 문제이다. 기존 dfs와 다른 점이라면 조건을 만족할 때 지나온 값들을 모두 정렬하여 출력해야 한다는 점이다. 그래서 중복을 제거해주고 정렬을 해주는 set을 이용했다. 1부터 N까지 반복문을 돌면서 dfs를 해준다. dfs를 하면서 지나온 값들을 set<int> tmp에 넣어주고 visit이 true인 지점에 도달했을 때 start, 즉 시작 지점에 도달했다면 이를 전역 변수인 set<int> res에 저장해주었다. 이를 반복해주며 res 값들을 구해 출력해주었다. 어렵지 않게 풀 수 있었다.

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

using namespace std;

int N;
vector<int> v;
set<int> res;
bool visit[101];

void dfs(int start, int next, set<int> tmp) {
    if (visit[next]) {
        if (start == next) {
            res.insert(tmp.begin(), tmp.end());
        }
        return;
    }

    visit[next] = true;
    tmp.insert(next);
    
    dfs(start, v[next], tmp);
}

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

    cout << res.size() << endl;
    for (auto elem : res) {
        cout << elem << endl;
    }
}

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

    cin >> N;

    int a;
    v.push_back(-1);
    for (int i = 0; i < N; i++) {
        cin >> a;
        v.push_back(a);
    }

    solution();

    return 0;
}