백준 9486번 - 텀 프로젝트

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

그래프 문제 중에서 사이클에 대한 개념을 알고 있는지에 대한 문제이다.

학생들이 함께 프로젝트를 하고 싶은 학생을 가리키고 있을 때 사이클에 대한 개수가 몇 개인지를 알면 된다.

처음에 이 문제를 풀었을 때 고민하다가 사이클에 대한 개수를 어떻게 구해야 할지 몰라서

결국 코드플러스 강의를 참고해서 문제를 풀 수 있었다.

우선 문제에 나와 있는 첫 번째 예시를 참고해서 어떻게 3이 나오는지를 확인해보자.

 

 

위의 그림을 보면 색칠된 부분이 사이클을 이루는 부분이며 총 4명의 학생이 팀을 이루게 된다.

이때 우리가 알아야 하는 것은 어떻게 4명을 구하느냐이다.

4, 6, 7번 학생의 경우에는 dfs를 통해 쉽게 구할 수 있어 보이지만

1, 2, 3, 5번 학생에서 3번만 사이클이 생성된다는 것도 고려해야 한다.

이때 중요한 것은 

1) 각각의 학생을 방문했는지에 대한 유무 (visited)

2) 방문할 때마다 몇 번 째로 방문했는지 (cnt)

3) 방문할 때 가장 첫 번째로 시작한 학생이 누구인지를 각각 비교해야 한다. (cycle 확인)

무슨 말인지 쉽게 감이 오지 않을 수도 있다.

나 역시 무슨 소리인지 감이 오지 않았는데 그림으로 이해해 보도록 하자.

 

 

처음 방문하는 학생을 1번이라고 지정하면 시작한 번호는 1이 될 것이다.

 

 

 

 

다음으로 3번을 방문하게 되면 시작한 번호는 1이 될 것이고 방문한 횟수는 2번째가 된다.

 

 

다음으로 3번 학생을 다시 방문하게 되면 시작한 번호는 1이 되는데

여기서 중요한 것은 3번은 이전에 방문하게 된 것이다.

 

 

즉 사이클이 발생하게 되는 것을 알 수 있다.

이때 2가지를 살펴보아야 한다.

1) 방문한 번호가 이전에 방문한 학생이 아닌, 즉 현재 구하려는 사이클에 해당하는지

2) 1번을 만족할 때, 사이클의 해당하는 학생은 몇 명인지

 

 

위에서 1번을 구하기 위해 우리는 시작 정점을 계속해서 저장한 것이다.

만약 시작 정점이 다르다면, 이전에 이미 다른 시작 정점에서 방문한 학생이기 때문에 사이클은 존재하지 않게 된다.

2번의 경우에는 시작 정점이 같더라도 어디서부터 어디까지가 사이클에 해당하는지를 구해야 하는 부분이다.

1번을 만족한다면 현재 방문했을 때의 횟수에서 이전에 방문했을 때의 값을 빼주면 된다.

즉, 위에서 3번 학생만 사이클을 이루는 것을 구할 때

3번 학생을 이전에 2번째로 방문했고 다음으로 3번째로 방문했을 때 기존에 2번째로 방문했기 때문에

3-2=1이 된다.

 

 

 

한 개가 아닌 여러 학생이 사이클을 이루는 경우를 예시로 보면 다음과 같다.

 

위에서는 1번 학생부터 시작했지만 3명의 학생만 사이클을 이루는 경우이다.

 

4번 학생이 다시 2번 학생으로 갈 때 2번 학생을 2번째로 방문했기 때문에 5번째에서 2번째를 빼주면 3이 된다.

즉 1번 학생을 사이클에 포함하지 않게 되는 것이다.

 

 

이런 방식은 아마 몇 날 며칠을 고민했어도 생각하지 못했을 것 같다.

항상 알고리즘을 풀 때마다 아직 부족한 점이 많고 정말 똑똑한 분들이 많다는 것을 느끼게 된다.

고민해도 풀리지 않는다면 다른 사람들의 문제 해결 방법을 보는 것도 좋은 방법인 것 같다.

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> student; //학생이 가리키는 다른 학생 번호
vector<int> first_student; //첫 번째로 dfs를 시작한 학생 번호
vector<int> visited; //방문 유무
 
int dfs(int start,int current,int cnt){
    
    if(visited[current]){
        
        //첫 번째로 dfs를 시작한 학생이 맞는지, 사이클이 맞는지
        if(first_student[current]!=start)
            return 0;
        
        //사이클에 해당되는 학생 수
        return cnt-visited[current];
    }
    
    first_student[current]=start;
    visited[current]=cnt;
    return dfs(start,student[current],cnt+1);
}
 
int main(){
    
    int T;
    cin>>T;
    
    int n;
    for(int testCase=0;testCase<T;testCase++){
        
        scanf("%d",&n);
        
        student=vector<int> (n+1,0);
        first_student=vector<int> (n+1,0);
        visited=vector<int> (n+1,0);
        
        for(int i=1;i<=n;i++)
            scanf("%d",&student[i]);
        
        int ans=0;
        for(int i=1;i<=n;i++){
            if(!visited[i]){
                ans+=dfs(i,i,1);
            }
        }
        
        printf("%d\n",n-ans);
    }
    
    return 0;
}