[BOJ / 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까지 번호가 부여된다.)

출력

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

Solved.ac 레벨

골드 III

풀이

문제를 읽자마자 그래프에서 사이클이 발생하는 경우를 판별해야된다고 생각했다.

이전에 크루스칼 알고리즘을 활용하는 MST 판별에서 합집합 알고리즘을 통해 사이클을 판별해낸다는 것을 알고 있었지만 문제 분류가 DFS이기에 DFS를 돌며 사이클이 발생하는 경우를 구해야했다. 

 

기존에 bool 타입으로 사용하던 방문탐색 배열 visited를 int 타입으로 활용하여 -1부터 시작해 DFS를 진행하며 depth를 늘려주는 방식으로 사용했다.

 

finished 배열은 해당 정점의 함수가 종료가 되었는지를 나타낸다. 만약 1번 노드에서 시작된 DFS 재귀 호출이 모두 완료되어 리턴되어 다시 1번 DFS를 종료할 시점에 1번 노드를 방문했으나 함수가 종료되지 않은 경우다. 이것은 해당 경로가 다시 시작점으로 돌와왔음을 의미하며 사이클이 발생했다는 뜻이다.

 

사이클이 발생했다면 visited 배열에 저장되어 있던 depth를 활용한다. 현재 파라미터로 주어진 정점의 depth에서 다음 정점 (다시 돌아온 시작 정점)을 빼주면 사이클을 이루고 있는 그래프의 노드 갯수를 알 수 있다.

 

따라서 사이클을 이루고 있는 노드 갯수를 전체 노드 갯수에서 빼주면 팀을 구하지 못한 학생들을 구할 수 있다.

 

Code

#include <bits/stdc++.h>

#define MAX 100001

using namespace std;

int node[MAX];
int visited[MAX] = {-1};
bool finished[MAX];
int t, ans, depth;

void DFS(int vertex) {

    visited[vertex] = depth++;
    int nxt = node[vertex];

    if(visited[nxt] == -1) {
        DFS(nxt);
    } else if(!finished[nxt]) {
        ans += visited[vertex] - visited[nxt] + 1;
    }

    finished[vertex] = true;
}


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

    cin >> t;

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

        memset(visited, -1, sizeof(visited));
        memset(finished, false, sizeof(finished));
        ans = 0;

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

        for (int i = 1; i <= n; i++) {
            if (visited[i] == -1) {
                DFS(i);

            }
        }

        cout << n - ans << "\n";
    }

    return 0;
}

9466번: 텀 프로젝트