백준 2668 / 숫자고르기

문제

풀이

각각의 배열 cycle[], visited[], value[]를 선언
cycle : 순환하는 원소를 구별하는 배열
visited : 첫째줄 넘버의 인덱스에 방문했는지 안 했는지를 구별하는 배열
value는 : 뽑은 값에 방문했는지 안 했는지 구별하는 배열

시간 복잡도 : O(N^3)

코드

#include <stdio.h>

int n, cnt, pick[111];
int cycle[111];
int visited[111];
int value[111];

void dfs(int num) {
    if (visited[num])
        return;
    visited[num]++;
    value[pick[num]]++;
    dfs(pick[num]);
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", pick + i);
    }

    for (int num = 1; num <= n; num++) {
        if (cycle[num])
            continue;
        
        for (int i = 1; i <= n; i++)
            visited[i] = value[i] = 0;
        
        dfs(num);

        int isCycle = 1;
        for (int i = 1; i <= n; i++) {
            if (visited[i] != value[i])
                isCycle = 0;
        }
        
        if (isCycle) {
            for (int i = 1; i <= n; i++) {
                if (visited[i]) {
                    cycle[i] = 1;
                    cnt++;
                }
            }
        }
    }

    printf("%d\n", cnt); // 출력
    for (int i = 1; i <= n; i++)
        if (cycle[i])
            printf("%d\n", i);
    
    return 0;
}

새로 알게된 지식

출처

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