백준 9466 - 텀 프로젝트

 

 

문제 설명

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

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

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

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

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 각 학생이 같이 팀이 되고 싶은 한 명을 선택했을 때, 몇 명이 팀을 이루지 못하는지 구하면 된다.

팀을 이루는 조건은 자신이 자신을 고르거나 모든 팀원이 서로를 한 번씩 선택한 경우이다.

즉, 사이클을 이루는 경우이다.

 

주어진 선택을 그래프로 생각하면 사이클을 이루는 노드의 개수를 구하는 문제로 대체할 수 있다.

한 가지 주의할 점은 사이클을 이루는 노드만 세어야 한다는 것이다.

예를 들어 보자.

6
2 3 4 5 6 2

이러한 상황에서 팀을 이루는 노드들은 1을 제외한 노드들이다.

즉, 5명의 학생만이 팀을 이룰 수 있다.

 

사이클을 판정하기 위해서는 DFS를 이용할 수 있다.

다음 노드로 진행하며 방문 여부를 확인하면 된다.

만약, 이미 방문한 노드라면 사이클이 발생했거나 이미 이전 노드들에 의해 방문된 노드일 것이다.

이전 노드에 의해 방문되지 않은 노드라면 사이클을 돌며 개수를 세면 된다.

for (int i = next; i != current; i = graph[i]) 
{
    cnt++;
}

cnt++;

이전 노드에 의한 처리 여부를 확인하지 않는다면 무한 반복에 걸릴 수 있다.

최초 사이클 방문시에는 문제없이 동작하지만 만약 해당 사이클에 또다시 접근하게 되면 이미 방문한 노드이기 때문에 사이클을 돌게 될 것이고 사이클이 반복되면서 i가 current로 가는 일 이 절대 없을 것이기 때문이다.

즉, 1번 노드에서 시작하여 사이클을 처리한 경우는 정상적으로 동작하지만 7에서 다시 한번 사이클에 접근하면 사이클을 돌면서 7로 되돌아가 종료되는 경우가 존재하지 않게 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
const int MAX = 100001;
int T, N;
int graph[MAX];
bool visited[MAX];
bool done[MAX];
int cnt;

void DetectCycle(int current) 
{
    visited[current] = true;
    int next = graph[current];

    if (!visited[next]) 
    {
        DetectCycle(next);
    }
    else if (!done[next]) 
    {
        for (int i = next; i != current; i = graph[i]) 
        {
            cnt++;
        }

        cnt++;
    }

    done[current] = true;
}


int main() 
{
    INPUT_OPTIMIZE;

    cin >> T;
    while (T--) 
    {
        cin >> N;
        for (int i = 1; i <= N; i++) 
        {
            cin >> graph[i];
        }

        for (int i = 1; i <= N; i++) 
        {
            if (!visited[i]) 
            {
                DetectCycle(i);
            }
        }

        cout << N - cnt << '\n';
        cnt = 0;

        memset(visited, false, sizeof(visited));
        memset(done, false, sizeof(done));
    }

    return 0;
}

---