[골드 3] 9466번: 텀 프로젝트

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

9466번: 텀 프로젝트

---

문제

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

학생들이 $ (s_1, s_2, \dots , s_r) $이라 할 때, $ r = 1 $ 이고 $ s_1 $이 $ s_1 $을 선택하는 경우나, $ s_1 $이 $ s_2 $를 선택하고, $ s_2 $가 $ s_3 $를 선택하고, … , $ s_{r - 1} $이 $ s_r $을 선택하고, $ s_r $이 $s_1 $을 선택하는 경우에만 한 팀이 될 수 있다.

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

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

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

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

입력

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

출력

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

---

풀이

기본적으로 생각해낼 만한 풀이 방법은 '처음부터 끝까지 학생들을 순회하되, bool 타입 방문 처리 배열을 하나 만들어서 방문하지 않은 학생만 DFS를 돌린다. DFS를 수행할 때 첫 번째 원소를 따로 저장한 뒤 첫 번째 원소가 다시 등장하면 하나의 사이클로 생각한다' 이다. 하지만 이렇게 하면 무한 루프에 빠지게 된다. 다음과 같은 경우를 생각해보자.

1	2	3	4	5
2	3	4	5	2

처음에 학생 $ 1 $을 선택해 DFS를 돌릴 때, $ 1 $ → $ 2 $ → $ 3 $ → $ 4 $ → $ 5 $ → $ 2 $ → $ 3 $ → $ 4 $ → $ 5 $ … 순서로 순회하게 된다. 이때 순회 과정에서 첫 번째 원소였던 $ 1 $을 찾을 수 없으므로 무한 루프에 빠진다.

첫 번째 원소가 재등장할 때 DFS를 종료하는 대신, 이미 방문한 원소가 다시 등장하면 종료하기로 해도 마찬가지다. DFS 종료 시 사이클을 순회하며 학생 숫자를 세는 과정에서 무한 루프에 빠지게 된다. 그래프 내에서 사이클을 순회할 때는 다음과 같은 코드를 사용한다.

for (int i = next; i != cur; i = graph[i]) {
	count++;
}

cur은 DFS가 종료되었을 때의 현재 노드, next는 그 다음 노드에 해당한다. 위 코드를 염두에 두면서 다음 경우를 생각해보자.

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

맨 처음 학생 $ 1 $을 선택했을 때는 정상적으로 DFS가 돌아간다. 문제는 학생 $ 2 $를 선택하는 경우다. 이미 학생 $ 3 $이 방문 처리가 되었기 때문에 cur은 $ 2 $, next는 $ 3 $이 된다. 따라서 사이클 안에 원소 $ 2 $가 없으므로 반복문의 종료 조건이 충족되지 않아 무한 루프에 빠진다. 또한 설령 무한 루프에 빠지지 않더라도 학생 수가 중복으로 세지므로 올바른 답을 구할 수 없다.

이 문제를 해결하는 방법은 방문 처리 배열을 두 개 만드는 것이다. 첫 번째 배열은 DFS를 돌면서 원소를 방문했는지 나타내고, 두 번째 배열은 원소가 이미 다른 사이클에 속해 있는지(혹은 사이클이 발생했을 때 순회되었던 원소인지)를 나타낸다. 그리고 DFS를 돌다가 다음 원소가 이미 방문한 원소일 때 + 다른 사이클에 속해 있지 않은 원소일 때 사이클의 원소 개수를 센 뒤 종료하면 된다. 이렇게 하면 모든 학생을 단 한 번씩만 방문하므로 $ O(N) $ 시간에 문제를 해결할 수 있다.

내가 작성한 소스코드

#include <iostream>
#define MAX 100000

using namespace std;

int T, N;
int graph[MAX];
bool is_visited[MAX];
bool is_cycle[MAX];
int count;

void find_cycle(int cur) {
    is_visited[cur] = true;
    int next = graph[cur];
    if (!is_visited[next]) {
        find_cycle(next);
    } else if (!is_cycle[next]) {
        for (int i = next; i != cur; i = graph[i]) {
            count++;
        }
        count++; // cur까지 포함하여 사이클의 크기 측정
    }
    is_cycle[cur] = true;
    return;
}

void search(void) {
    for (int i = 0; i < N; i++) {
        if (is_visited[i]) continue;
        find_cycle(i);
    }
    return;
}

void init(void) {
    for (int i = 0; i < N; i++) {
        is_visited[i] = false;
        is_cycle[i] = false;
    }
    count = 0;
    return;
}

void input(void) {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> graph[i];
        graph[i]--; // 번호가 0부터 시작하도록 조정
    }
    return;
}

void output(void) {
    cout << N - count << "\n";
    return;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> T;
    for (int i = 0; i < T; i++) {
        input();
        init();
        search();
        output();
    }
    return 0;
}

남이 작성한 소스코드

꾸준함 님:
https://jaimemin.tistory.com/674