백준 2668 숫자 고르기

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

2668번: 숫자고르기

처음문제를 접했을때 그냥 한개씩 첨부터 끝까지 확인해보변 되겠다 했는데 

N이 100개인것을 보고 그대로 하면 시간초과 날것 같다 생각하여 

주어진 표를 보면서 어떤 방식이 좋을지 생각을 해보았습니다.

그래서 뭔가 그래프 경로 같은 느낌이 들었습니다.

저만 그런가요? 무튼 저는 그냥 일단 연결을 해보았습니다.

1부터

7까지 각 각 연결을 해보고 놀랐습니다.

답이 되는 1 , 3,  5과 어떤 규칙을 가지는지 눈에 보이시나요?

안보이신다면 말씀드리겠습니다. 자기번호로 시작해서 자기번호로 다시오는

완전한 사이클을 갖는다는것을 알수 있었습니다. 완전한 사이클을 가진 번호를 뽑으면

여기서 1 3 5 카드를 뽑으면 그 카드에도 1 3 5라는 숫자가 있는것이 정답이기때문에

사이클을 가진다면 뽑은 숫자의 숫자와 일치하기 때문에 이런 방식으로 하면 되겠다 생각

했습니다.

자기 자신의 번호로 시작해서 dfs를 이용해서 자기 자신의 번호로 오는 번호만

배열에 저장해서 갯수와 입력된 값을 출력하면 끝 완전 쉽지 않습니까?

아래 소스를 보고 이해하시면 더좋습니다.

 

#include<stdio.h>
#include<string.h>
using namespace std;
int N;
int map[101];
int chk[101];
int idx = 0;
int num[101];
int dfs(int target_num, int current_num) {
    if (chk[current_num] == 0) {;
        chk[current_num] = 1;
        dfs(target_num, map[current_num]);
    }
    else {
        if (target_num == current_num) return 1;// 사이클이다.
        else return 0;//사이클이 아니다.
    }
}
int main(void) {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &map[i]);
    }
    for (int i = 1; i <= N; i++) {
        if (dfs(i, i)) {
            num[idx++] = i;
        }
        memset(chk, 0, sizeof(chk));
    }
    printf("%d\n", idx);
    for (int i = 0; i < idx; i++) {
        printf("%d\n", num[i]);
    }
    return 0;
}

여기서 포인트는 방식을 빨리 캐치하는가 , 사이클 확인 소스를 짤수 있는지 판단하는것

같습니다. 오늘은 여기까지 이고 오늘도 고생많으셨습니다.