[C++] 백준 온라인 저지 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는 어느 팀에도 속하지 않는다.

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

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

 

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

 

 

풀이

 

 보자마자 DFS로 쉽게 풀 수 있을거라 생각했는데 암만 최적화를 해도 84%에서 계속 시간초과가 나서... 시간을 많이 쓴 문제였습니다.

 처음엔 DFS를 통해 사이클이 형성된 노드들은 더 이상 탐색하지 않고 사이클이 형성되지 않은 노드들에 한해서 재탐색하는 구조로 짰었는데요... 이렇게 하면 방문했지만 사이클이 이루어지지 않은 노드는 다시 반복해야 하기 때문에 노드를 한 번만 방문하는 것이 아닌데다 각 노드에서 DFS 탐색이 이루어 질 때마다 최악의 경우에는 n번의 탐색을 반복하게 되기 때문에 O(N^2)의 풀이가 되었던 것 같습니다. 한마디로 최악의 경우엔 2중 for문을 돌리는 꼴이었음... 

 그래서 구글링 후 

https://ongveloper.tistory.com/167

백준 9466 텀 프로젝트 c++ (dfs)

 

https://jaimemin.tistory.com/674

백준 9466번 텀 프로젝트

 

 이 두 블로그를 참고하여 O(N)번만 탐색하도록 로직을 수정한 후 통과할 수 있었습니다. 

 

 수정한 로직은 visited 배열 외에 done 배열도 사용해 해당 노드까지 사이클이 이루어 졌는지도 확인합니다. 다음에 방문할 노드가 이미 방문한 노드인데 done 배열에서는 false인 상태라면 상태라면 현재 위치부터 사이클이 이루어지는 노드들의 갯수를 센 다음 사이클을 이루는 노드들을 done 배열에서 모두 true로 바꿔주는 것이죠. 이렇게 하면 다음부터는 방문했으면서 사이클이 이루어진 노드는 탐색하지 않기 때문에 모든 노드를 1번만 방문할 수 있으면서 사이클이 이루어졌는지 아닌지에 대한 확인도 함께 할 수 있습니다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int answer = 0;
void dfs(vector<int>& students, vector<bool>& visited, vector<bool>& done, int cur)
{
    visited[cur] = true;
    int next = students[cur];
    
    if (!visited[next])
    {
        //방문하지 않았으면 dfs 재귀호출
        dfs(students, visited, done, next);
    }
    else if (!done[next])
    {
        //다음 노드를 방문은 했지만 사이클이 이루어지지 않았으면 사이클을 이루는 노드들의 갯수를 센다.
        int count = 0;
        //i가 노드 번호를 타고 가면 사이클을 이루는 노드들을 찾을 수 있다.
        for (int i = next; cur != i; i = students[i])
            count++;
        
        //현재 노드도 더한 값을 빼준다.
        answer -= ++count;
    }
    
    done[cur] = true;
}

int main()
{
    int T;
    cin >> T;
    
    for (int i = 0; T > i; i++)
    {
        int size;
        cin >> size;
        vector<int> students(size + 1);
        for (int j = 1; size >= j; j++)
            cin >> students[j];
        
        answer = size; //모든 학생이 팀을 이룰 수 없다고 가정하고 시작
        vector<bool> visited(size + 1, false); //방문확인 배열
        vector<bool> done(size + 1, false); //사이클 확인 배열
        for (int j = 1; visited.size() > j; j++)
        {
            if (!visited[j])
                dfs(students, visited, done, j);
        }
        
        cout << answer << "\n";
    }
    
    return 0;
}