[백준 9466번] 텀 프로젝트 (C++)

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

9466번: 텀 프로젝트

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, result;
int arr[100001];
int visited[100001];

void func(int idx)
{
    int cur = idx;
    while(1)
    {
        visited[cur]=idx;
        cur = arr[cur]; //연결된 값으로 교체
        if(visited[cur]==idx) //사이클 발생
        {
            while(visited[cur]!=-1)
            { 
                visited[cur]=-1; //사이클 내에 팀 선택처리
                cur=arr[cur]; //연결된 다음 값으로 교체
            }
            return;
        }
        if(visited[cur]) return; //이미 탐색했었다면 종료
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int T;
    cin >> T;
    while(T--)
    {
        cin >> N;
        result = 0;
        memset(visited, 0 , sizeof(visited));
        memset(arr, 0, sizeof(arr));
        for(int i=1; i<=N; i++) cin >> arr[i];
        for(int i=1; i<=N; i++) if(visited[i]!=-1) func(i); 
        for(int i=1; i<=N; i++) if(visited[i]!=-1) result++; //포함안된 것만 카운트
        cout << result << "\n";
    }
    return 0;
}

처음에 풀고 시간초과가 나서 다소 검색을 해보고 풀게된 문제이다.

 

문제를 읽어 보면 팀에 속한다는 것은 사이클을 이룬 경우라는 것을 알 수 있다.

(학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.)

따라서 사이클을 확인해야 하는데 단순히 모두 확인하면 시간초과가 발생하기에 이미 방문한 값은 넘겨야 한다.

 

먼저 해당 위치 별로 사이클을 탐색하며, 사이클이 발생했다면 해당 사이클 내에 값들을 -1로 저장해준다 (팀 선택 처리)

사이클이 발생하지 않았다면 그대로 탐색을 하는데 만약 이미 탐색한 값을 또 방문하게 된다면 바로 종료시켜준다.

이를 모든 위치에 대해서 반복해서 실행하는데 해당 위치에 대해서도 이미 그 전 위치에서 사이클을 탐색하며 방문했을 수도 있기 때문에 이런 경우도 중복 탐색을 방지하도록 해준다.

 

모든 탐색을 마치고 사이클 내에 들지 못한 값들만 (-1이 아닌 값들만) 따로 카운팅하여 출력해준다.

 

1 2 3 4 5 6 7
3 1 3 7 3 4 6

1 -> 3 -> 3 (3, 3 사이클 발생 visited[3]=-1)

2 -> 1 (1은 위에서 이미 방문 했으므로 탐색 종료)

3 (3은 사이클로 인해 이미 전에 방문했으므로 탐색 종료)

4 -> 7 -> 6 -> 4 (4, 7, 6, 4 사이클 발생 visited[4]=-1, visited[7]=-1, visited[6]=-1)

5 -> 3 (3은 사이클로 인해 이미 전에 방문했으므로 탐색 종료)

6 (6은 사이클로 인해 이미 전에 방문했으므로 탐색 종료)

7 (7은 사이클로 인해 이미 전에 방문했으므로 탐색 종료)

사이클로 인해 실질적인 탐색 시작은 1, 2, 4, 5만 실행

 

풀고 나서 백준 게시판을 보니 위상정렬을 이용하여 간단하게 풀 수 있다는 것을 알았다.

위상정렬을 할 때 방문하지 못한 정점이 발생했다면 이는 사이클을 이룬다는 것이다.

이를 이용하여 위상정렬을 할 때 방문한 정점들의 갯수가 사이클을 이루지 않은 (=팀에 포함되지 못한) 갯수라는 것을 알 수 있었다.