[9466번] 텀 프로젝트

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Union Find의 Find 방식

2. 집합

유니온 파인드의 파인드 방식을 생각하면서 풀면 이해하기가 좀 더 쉽다.(사이클에 대한 개념을)

이 문제는 3가지 경우로 나눌 수 있다.

이 세가지 방식에 대해 처리를 해주면 쉽게 해결 할 수 있다.

단, 노드를 하나씩 방문하는 것이 아닌, 이미 사이클 탐색을 시작하는 순간 그 노드들은 방문했는 것으로 처리해도 된다는 것이다.

예를들어 3번째그림의 모습을 보면 1->2->3->4->2로 반복되는데 2,3,4는 사이클이지만 1은 사이클이 아니다.

따라서 1을 탐색한 순간 2,3,4도 모두 탐색이 완료된 상태로 생각 할 수 있다.

소스 코드를 통해 어떻게 탐색을하고 탐색한 노드를 어떻게 처리하는지 알아보자.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <vector>
 
using namespace std;
 
int parent[100002];
int visit[100002];
int prevNum[100002];
 
int cycleTest;
vector<int> cycle;
 
int isCycle(int root, int prev, int here, int cnt)
{
    // 이미 체크된 노드에 대해서는 return -1
    if (parent[here] == -1)
        return -1;
 
    // 현재 cycleTest번째에 이미 방문한 적이 있는가?
    if (visit[here] == cycleTest)
    {
        // 시작->끝이 사이클인가?
        if (here == root)
            return cnt - 1;
 
        // 시작->끝이 사이클이 아니라면 사이클이 그사이 존재했는것
        // 따라서 꼬리부분을 제외한 사이클 부분을 return
        return cnt - prevNum[here];
    }
 
    // 자신의 뒷부분에 따라오는 노드를 추가
    prevNum[here] = prevNum[prev] + 1;
    
    // here은 cycleTest번째에 방문을 하고있다
    visit[here] = cycleTest;
    // 그에 해당하는 here을 벡터에 담아둔다.(사이클이든 아니든)
    cycle.push_back(here);
 
    return isCycle(root, here, parent[here], cnt + 1);
}
 
 
int main()
{
    int tCase;
 
    scanf("%d", &tCase);
 
    while (tCase--)
    {
        int n;
        int ans = 0;
 
        scanf("%d", &n);
 
        for (int i = 1; i <= n; i++)
            scanf("%d", &parent[i]);
 
        for (int i = 1; i <= n; i++)
        {
            // 이미 체크된 노드라면 continue;
            if (parent[i] == -1)
                continue;
            
            // cycleTest번째를 늘려준다.(visit를 memset하는것 대신 이용)
            cycleTest++;
            cycle.clear();
            // get에는 사이클의 크기가 담겨온다.
            int get = isCycle(i, 0, i, 1);
            
            // 사이클이 존재한다면
            if (get != -1)
            {
                ans += get;
                cycleTest++;
            }
            
            // 사이클이었든 아니었든 벡터에 담긴 값들은 모두 -1로 없앤다.
            int len = cycle.size();
            for (int i = 0; i < len; i++)
                parent[cycle[i]] = -1;
        }
 
        // 전체 노드 - 사이클을 이룬 수
        printf("%d\n", n - ans);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>