9466: 텀 프로젝트

• toc {:toc}

문제 확인하기

풀이

문제에 대한 설명을 시각화하면 다음과 같다.

다음의 그래프 구조의 특징은 다음과 같다.

1. 방향이 있다.
2. 사이클이 발생할 수 있다.
3. 자기 자신을 선택하는 루프가 있다.

보다 더 쉽게 시각화하면 다음과 같다.

1, 2, 3, 5는 3이 자기 자신을 선택했기 때문에 사이클이 만들어지지 않는다. 반면, 4, 6, 7은 사이클이 만들어져 결과값의 대상에서 제외된다.

풀이 방식은 다음과 같다.

1. 1부터 전체 수를 반복하여 방문한 적이 없다면 cycle 함수에 넣어준다.
2. cycle 함수를 통해 사이클을 체크해준다.
3. 사이클에 들어가 있지 않은 수를 체크해준다.

cycle 함수의 풀이 방식은 다음과 같다.

1. x를 체크값이라 생각한다. 방문체크는 체크값으로 진행한다. vis[cur] = x;
2. 해당 함수 안에서 즉, 위 그림에서 x=4이고 사이클을 돌아 다시 4로 이동한 경우이다. 해당 경우 체크값이 x이기 때문에 vis[cur]== x 라면 -1로 사이클이라는 것을 체크해준다.
3. 만약, 현재 x=6 일 때를 생각하면 x=4일 때 이미 사이클이 한 번 체크가 된 상황이다. 때문에 사이클을 다시 확인할 필요없이 반환한다.
4. vis 가 -1이 아닌 경우, 즉, 사이클이 아닌 경우 res++을 통해서 팀에 해당하지 않는 경우를 체크한다.

#include <bits/stdc++.h>
using namespace std;
 
int vis[100005];
int students[100005];
int n;
 
void cycle(int x){
    int cur = x;
    while(true){
        vis[cur] = x;
        cur = students[cur];
        if(vis[cur] == x){
            while(vis[cur] != -1){
                vis[cur] = -1;
                cur = students[cur];
            }
            return;
        }
        else if(vis[cur] != 0) return;
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
 
    cin >> T;
 
    while(T--){
        cin >> n;
        fill(vis, vis+n+1, 0);
        for(int i=1; i<=n; i++){
            cin >> students[i];
        }
        int res = 0;
        for(int i=1; i<=n; i++){
            if(vis[i] == 0) cycle(i);
        }
        for(int i=1; i<=n; i++){
            if(vis[i] != -1) res++; 
        }
        cout << res << '\n';
    }
 
    return 0;
}