백준 9466 - 텀 프로젝트

문제

 

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

9466번: 텀 프로젝트

 

 

풀이

 

모든 탐색의 끝은 사이클을 이루게 되므로 마지막에 방문한 정점을 기준으로 사이클을 검사하면 된다. 그리고 사이클을 계속 순환하면 안되므로 dfs 탐색에서 사용하는 visit 배열에 추가로 done 배열을 이용해서 사이클 탐색을 실행한다. 사이클 탐색을 실행한 정점들의 done 배열 값을 true로 만들어 준다. 그러면 dfs 탐색도 하고 사이클 검사도 햇으므로 더 이상 그 정점은 방문을 하지 않아도 된다.

 

문제에서 먼저 1 3 3 순서로 정점을 방문한다. dfs 탐색은 3번 정점에서 끝나게 되고 3번 정점을 기준으로 다시 사이클 검사를 실행하면 된다. 3번과 연결된 정점은 3번 뿐이므로 사이클 검사가 끝나게 되고 1번 정점과 3번 정점의 done 값을 true로 해준다.

 

그 다음에는 2번 정점에서 dfs가 시작되어 2 1 3 3 으로 되는데 이미 1번 정점에 방문 결과가 나왔기 때문에 2번 정점에서 더 이상 진행할 탐색은 없게 된다.

 

다음으로 문제에서 4 7 6 -> 4 7 6 ... 이렇게 사이클을 형성한다. 이때 4번 정점은 이미 방문 했기 때문에, 6번 정점에서 4번 정점으로 dfs를 진행할 수 없다. 이때도 6번 정점을 기준으로 사이클을 검사하면 된다.

 

문제에서 팀을 구하지 못한 학생 수를 구하라고 했으므로 

전체 학생 수 - 팀에 속한 학생 수 로 

답을 구한다. 

 

 

코드

 

#include <iostream>
 
using namespace std;
 
const int MAX = 100001;
 
int n, T;
int graph[MAX];
bool visit[MAX];
bool done[MAX];   
int cnt;
 
void dfs(int v)
{
    visit[v] = true;
    int next = graph[v];
    if (!visit[next]) dfs(next);
    if (!done[next]) // 사이클
    {
        // 사이클 안에 노드 개수 검사
        for (int c = next; c != v; c = graph[c]) cnt++;
        cnt++;
    }
    done[v] = true;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> T;
    while (T--)
    {
        cin >> n;
 
        for (int i=1; i<=n; i++) graph[i] = visit[i] = done[i] = 0;
        cnt = 0;
 
        for (int i=1; i<=n; i++) cin >> graph[i];
        
        for (int i=1; i<=n; i++) if(!visit[i]) dfs(i);
 
        cout << n - cnt << '\n';
    }
 
    return 0;
}