백준 2668: 숫자 고르기 [C언어], 정보올림피아드

 

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

2668번: 숫자고르기

 

#include <stdio.h>
int n, cnt, lis[111]; // 입력, 답, 입력
int cycle[111]; // 사이클 유무
int visited[111]; // 1~N 중 방문한 곳
int value[111]; // 입력 값 중 방문한 곳
void dfs(int num) {
    if (visited[num]) return; // 이미 방문한 곳이면 더 방문할 필요가 없다
    visited[num]++; // 순서대로인 정수가 방문했다
    value[lis[num]]++; // 입력 값이 방문했다.
    dfs(lis[num]); // 입력 값을 방문한다
}
int main(void) { 
    scanf("%d", &n); // 입력
    for (int i = 1; i <= n; i++) scanf("%d", lis + 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;
}
 
 

총 걸린시간: 00:22:06

 

생각한 시간 : 00:11:01 

코드 작성 시간 :  00:11:05 

 

풀이:

입력 -

N	1	2	3	4	5	6	7
lis	3	1	1	5	5	4	6

해설 -

1. DFS를 하며 인덱스의 값과 입력값을 구하고, 서로 같은지 확인합니다.

 

1-1

인덱스의 값	1	3
입력 값	3	1

위의 예시는 인덱스의 값과 입력 값이 서로 같으니 cycle입니다.

 

1-2

인덱스의 값	6	4	5
입력 값	4	5	5

위의 예시는 인덱스의 값과 입력 값이 서로 다르니 cycle이 아닙니다.

 

2. 모든 인덱스에 대하여 '1. DFS를 하며 인덱스의 값과 입력값을 구하고, 서로 같은지 확인합니다.' 을 실행합니다.