[BOJ] 9466 텀 프로젝트

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

 내가 사이클에 무지하게 약하다는 것을 깨닫게 해준 문제다. 문제 자체는 특별할 게 없음에도 불구하고 이렇게 헤메는 걸 보면 망한 것 같다... 처음에 시작한 정점을 따로 체크해두고 처리하면 되는 문제였는데 코드를 좀 더 깔끔하게 짜 보겠다고 괜히 엉뚱하게 푼 것 같다. 보니까 다른 사람들도 다 이런 비슷한 방식으로 푼 것 같다. 만약 이미 사이클이 처리된 정점에 도달했다면 (색깔이 다르면) 그냥 바로 0을 반환하는 것으로 시간 초과를 막았다. 나는 개인적으로 1.75/5정도는 주고 싶은데 다른 사람들은 훨씬 쉽게 푼듯.

// input your code h#include <cstdio>
#include <vector>
 
using namespace std;
 
int dfs(vector<int> &arr, vector<int> &check, int x, int color)
{
    int s=0;
    if(check[x]==0)
    {
        check[x]=color;
        return dfs(arr,check,arr[x],color);
    }
    else
    {
        if(color!=check[x]) return 0;
        int wh=x;
        do
        {
            s++;
            check[wh]=color;
            wh=arr[wh];
        }while(x!=wh);
        return s;
    }
}
 
void solve()
{
    int n,s=0;
    scanf("%d",&n);
    vector<int> arr(n+1),check(n+1);
 
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
 
    for(int i=1;i<=n;i++)
        s+=dfs(arr,check,i,i);
    printf("%d\n",n-s);
}
 
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
    return 0;
}