[BOJ] 백준 2668 숫자 고르기

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

 Input 

7

3

1

1

5

5

4

6

　 

 Output 

3

1

3

5

윗줄에서 N ~ 0개의 정수를 뽑아서 둘째 줄과 조합되는 경우를 완전 탐색하는 경우는 TLE 발생

DFS 탐색으로 그래프 탐색하듯이 cycle이 형성되는 구간을 찾는 문제입니다.

첫째 줄: [1   2   3   4   5   6   7]

둘째 줄: [2   3   4   2   6   1   7]

① for문으로 각 정점을 출발점으로 DFS 탐색합니다.

    이때, 이미 조사가 끝난 구간(visited[])는 그냥 넘어갑니다. 

② DFS 탐색에서 cycle 구간을 파악하기 위해서는 chk[] 배열에 표시합니다.

    한번의 DFS탐색이 끝났을 때, 표시한 chk[] 값을 다시 해제합니다.

③ chk[]로 DFS 탐색 시 특정 구간에서 cylce이 발생하는 것을 알 수 있습니다.

    해당 지점부터 어느 지점까지 cycle 구간인지 확인한 후 개수와 cycle[]에 표시합니다.

 

[시뮬레이션]

① 정점 [1] 기준

    2 → 3 → 4 → 2에서 cycle [2, 3, 4]가 발생하는 것을 확인할 수 있습니다.

    visited[] = [T   T   T   T   F   F   F]

② 정점 [2], [3], [4]는 visited[]를 통해 이미 확인된 정점이므로 continue

③ 정점 [5] 기준

    6 → 1 → 2 → 3 → 4 → 2에서 이미 [2, 3, 4]는 cycle 표시하였으므로 추가적인 작업은 하지 않습니다.

    즉, 이미 cycle 영역에서 추가될 수 없으며, 독립적인 cycle을 형성해야 합니다.

    visited[] = [T   T   T   T   T   T   F]

④ 정점 [6]은 visited[6] == true이므로 continue

⑤ 정점 [7]은 정점 1개로써 cycle을 형성할 수 있으므로 추가됩니다.

    visited[] = [T   T   T   T   T   T   T]

▶ 답: 4개 (2, 3, 4, 7)

---

#include <stdio.h>
 
const int MAX_N = 100 + 5;
int N, ans;
int card[MAX_N];
bool visited[MAX_N], chk[MAX_N], cycle[MAX_N];
 
void DFS(int idx) {
    
 
    // cycle 여부 조사가 끝난 곳 표시
    visited[idx] = true;
 
    // 이미 방문한 곳을 재방문 하는 경우 cycle 형성
    if (chk[idx]) {
        if (cycle[idx]) return;
        int pivot = idx;
        int next = card[idx];
        cycle[pivot] = true;
        ans++;
        while (true) {
            if (next == pivot) return;
            cycle[next] = true;
            ans++;
            next = card[next];
        }
    }
    
    chk[idx] = true;
    DFS(card[idx]);
    chk[idx] = false;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
 
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &card[i]);
    }
 
    for (int i = 1; i <= N; ++i) {
        if (visited[i]) continue;
        DFS(i);
    }
 
    printf("%d\n", ans);
    for (int i = 1; i <= N; ++i) {
        if (cycle[i]) printf("%d\n", i);
    }
}