[BOJ] 9466번 - 텀 프로젝트

백준 9466번 - 텀 프로젝트

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초	256 MB	26205	6228	4013	24.813%

문제

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

학생들이(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까지 번호가 부여된다.)

출력

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

---

예제 입력 1

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

예제 출력 1

3
0

출처

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

접근 방법

1차 시도

문제의 요구 조건을 확인하였을 때, 사이클을 형성하는 노드들의 집합을 확인하는 과정이 필요하다.

모든 정점에서 DFS를 돌려서 사이클을 형성 한다면, 해당 정점들의 state를 2로 설정 하는 작업을 해주면 되지 않을까?

결과는 TLE였다..

 

2차 시도

모든 정점에서 DFS를 돌릴 필요가 없다는 것을 깨달았다.

DFS 수행 이 후, 팀을 형성할 수 없는 노드들은 다른 정점을 시작으로 DFS를 수행하더라도 절대 팀을 이룰 수 없기 때문이다.

DFS를 수행한다면, 시작 정점과 연결 된 모든 노드들을 탐색하며 팀을 이룰 수 있는지에 대한 여부를 확인한다.

DFS를 수행했을 때 시작 정점과 연결되어 있는 노드들은 모두 팀 형성 여부가 결정 된다.

방문했던 노드를 다시 탐색하는 것은 불필요하므로, 시작 정점과 연결되어 있지 않은 노드들에 대해서 DFS를 수행해주면 된다!

 

일단, DFS로 모든 정점들을 탐색하며 사이클을 이루는 정점들을 찾기 위해 DFS를 수행하며 방문한 노드들의 경로 값인 path 를 저장하였다.

 

사이클을 이루는 경우를 확인하기 위해서, 이 때 까지 방문한 경로에 다음에 방문할 정점이 포함되어 있는 지를 확인하면 된다. 

매번, path를 선형 탐색하는 방법 보다는 다음 노드의 상태(state) 값이 visited일 경우에만 확인 하는 것이 효율적이다.

다음 노드의 상태 값이 VISITED일 경우, 방문한 노드를 다시 방문하는 경우가 된다.

방문한 노드를 다시 방문하는 경우가 바로 우리가 찾는 사이클을 형성하는 경우이므로 path 상에서 해당 노드 이후 부터 현재까지 방문한 노드까지 모두 팀을 이룬다고 체크를 해주면 된다.

 

 

 

 

소스 코드

#define NOT_VISITED 0
#define VISITED 1
#define HAS_TEAM 2
#include <bits/stdc++.h>
using namespace std;
vector<int> students;
vector<int> state;
vector<int> path;
void DFS(int cur){
    int next = students[cur];
    if( state[next] == NOT_VISITED ){
        state[next] = VISITED;
        path.push_back(next);
        DFS(next);
        path.pop_back();
    }
    else{
        int idx = -1;
        for(int i=0; i<path.size(); i++){
            if( path[i] == next ){
                idx = i;
                break;
            }
        }
        if( idx == -1 ) return;
        for(int i=idx; i<path.size(); i++){
            int j = path[i];
            state[j] = HAS_TEAM;
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n ;

        students.resize(n+1), state.resize(n+1);
        for(int i=1; i<=n; i++){
            state[i] = NOT_VISITED;
        }

        for(int i=1; i<=n; i++){
            cin >> students[i];
        }

        for(int i=1; i<=n; i++){
            // 한번 순회를 해서, cycle 확인이 안된 것은 다시 확인 할 필요가 없다.
            // 연결되어있는 그래프들은 전부 cycle 여부가 check된다.
            if( state[i] != NOT_VISITED )
                continue;
            path.push_back(i);
            state[i] = VISITED;
            DFS(i);
            path.pop_back();
        }

        int cnt = 0;
        for(int i=1; i<=n; i++){
            if( state[i] != HAS_TEAM )
                cnt += 1;
        }
        cout << cnt << '\n';
    }

    return 0;
}