텀 프로젝트

코드

[ 반복문 풀이 ]

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std; 
int T, N;
int arr[100001];
int done[100001];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--)
    {
        fill(done, done+100001, -1);
        cin >> N;
        for(int i=0;i<N;i++)
        {
            cin >> arr[i+1];
            if(arr[i+1] == i+1) done[i+1] = 7;
        }
        for(int i=1;i<=N;i++)
        {
            if(done[i] == 7 or done[i] == 4) continue;
            vector<int> v;
            bool flag=false;
            int next = arr[i];
            done[i] = 0;
            v.push_back(i);
            while(done[next] == -1)
            {
                v.push_back(next);
                done[next] = 0;
                next = arr[next];
                if(arr[next] == next)
                    flag = true;
            }
            if(next == i){
                for(int k=0;k<v.size();k++)
                    done[v[k]] = 7; // 팀을 이루는데 성공한 사람
            }else if(flag){
                for(int k=0;k<v.size();k++)
                    done[v[k]] = 4; // 결국 마지막 원소가 자기 자신이므로 해당 그래프 모든 점은 팀이될 수 없음
            }else
            {
                /* 원상 복귀 - 중간에 정답이 있을 수 있기 때문 */
                for(int k=0;k<v.size();k++)
                    done[v[k]] = -1;
                done[i] = 4; // 팀 만들기 실패한 사람
            }
        }
        int cnt=0;
        for(int i=1;i<=N;i++)
            if(done[i] == 4) cnt++;
        cout << cnt <<'\n' ;
    }
    return 0;
}

• 깨달은 것
  • 자꾸 시간초과가 왜나는지 봤더니 무심코 for(1~N)안에서 done[]를 초기화 시켜준 것 때문이었음
    : fill()함수는 결국 O(N)의 시간이 거리는걸 간과하고 있었다.
  • 무심코 쓰는 STL 함수의 시간복잡도를 잊지 말자;

• 핵심
  • arr[]에 숫자를 입력받고 확실하게 끝난 것을 의미하는 done[]을 유지하며 검사하면 방문했던 점들은 임시로 0을 가지고, 팀 결정에 실패했으면 4 / 성공했으면 7 / 초기값 -1을 가진다.
    (-1 / 0 / 4 / 7)

---

[ DFS 풀이 ]

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std; 
int T, N, cnt;
int arr[100001];
bool vis[100001];
bool done[100001];
void DFS(int n){
    vis[n] = true;
    int next = arr[n];
    if(!vis[next])
        DFS(next);
    else if(!done[next]){
        // 사이클 검사 -> 방문 했던 점들 중 끝나지는 않았다면 무조건 사이클!
        for(int i=next;i!=n;i=arr[i])
            cnt++;
        cnt++; // 자기 자신
    }
    done[n] = true;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--)
    {
        cnt=0;
        fill(done, done+100001, false);
        fill(vis, vis+100001, false);
        cin >> N;
        for(int i=0;i<N;i++)
            cin >> arr[i+1];
        for(int i=1;i<=N;i++)
            if(!vis[i])
                DFS(i);
        cout << N-cnt << '\n';
    }
    return 0;
}

---

• 핵심
  • 정점들 간 순환(Cycle)을 검사하기 위해 vis[]와 done[] 사용
    : 순환의 조건은 vis[]==true && !done[] 일 때! 즉, 방문은 했으나 끝나지 않았으면 순환이다!
  • 순환하는 수를 계산한 후 전체 수에서 뺀다 (N-cnt)