[C++] BOJ 2668 숫자고르기

2668번: 숫자고르기

해당 문제는 일차원 배열에서 ‘사이클’ 을 구하는 문제이다. N이 100 이하이기 때문에 방문지를 체크하면서 DFS 를 구현만 하면 되는 문제인데 코드를 최적화하면서 신기하고 깔끔한 코드를 보게 되어서 공유하려고 한다.

#include<bits/stdc++.h>

using namespace std;

#define SIZE 102
int n, arr[SIZE], chk[SIZE], res;

void DFS(int x, int target) {
    for (int i = 1; i <= n; i++) {
        if (x == target) {
            res++, chk[x]++;
            return;
        }
        x = arr[x];
    }
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1; i <= n; i++) DFS(arr[i], i);
    cout << res << '\n';
    for (int i = 1; i <= n; i++)
        if (chk[i])
            cout << i << '\n';
    return 0;
}

x = arr[x] 한문장으로 재귀를 완성하는 코드이다. 박성훈님의 블로그를 보고 참고했다

Koder / 박성훈