[백준-9466] 텀 프로젝트

트릭이 필요한 탐색 문제였다.

일단 기존 DFS 를 사용해서 단순하게 check 하며 탐색한다. 이 때 cycle 이 생기는 경우 해당 cycle 에 포함되지 않는 노드의 개수를 구하기 때문에 visit 배열을 하나 더 만든다. 그 후 다음과 같은 규칙을 세운다.

• check는 color 로 칠하되 다른 컬러의 check 를 만났다면 그건 이미 만들어진 cycle 이므로 해당 color 구축시에는 cycle 노드 개수가 0이다. (0 return)
• check 가 0으로 되어있어 순회하는 경우 visit 배열에 몇 개의 노드를 탐색 중인지 메모해놓는다.
• check 가 color 로 칠해져있는 노드에 다시 한번 더 접근한 경우 해당 color 단계에서 cycle 이 발생했다는 것이다. 이 때 visit 에 저장되어있는 탐색 노드 개수를 전체 cnt 탐색 수에서 빼주게 되면 cycle 노드의 개수가 된다.
• 즉, dfs 의 결과값을 전체 노드의 개수에서 차근차근 빼주면 cycle 에 속하지 않는 노드의 개수가 만들어진다.

말이 좀 어려운데 기본적으로 color dfs 처럼 check 배열 순회 탐색을 진행한다. 거기에다가 visit 배열 하나만 추가해주어서 몇개의 노드를 탐색 중인 건지를 저장해 cycle 을 만드는 노드의 개수를 확인할 수 있게만 해주면 끝난다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <string.h>

#define INF 100000000

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

int arr[100001];
int check[100001];
int visit[100001];
int n, t;

int dfs(int x, int color, int cnt) {
    int next = arr[x];
    if (check[next]) {
        if (check[next] == color) {
            return cnt - visit[next];
        }
        else return 0;
    }
    else if (!check[next]) {
        check[next] = color;
        visit[next] = cnt;
        return dfs(next, color, cnt+1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        memset(check, 0, sizeof(check));
        for (int j = 1, input ; j <= n; j++) {
            cin >> arr[j];
        }
        int res = n;
        for (int j = 1, color = 1; j <= n; j++) {
            if (check[j] == 0) {
                check[j] = color;
                visit[j] = 0;
                res -= dfs(j, color++, 1);
            }
        }

        cout << res << endl;
    }



    return 0;
}

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

9466번: 텀 프로젝트