[BOJ] 9466 텀 프로젝트

문제 링크

• https://www.acmicpc.net/problem/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까지 번호가 부여된다.)

출력

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

---

생각

이 문제는 결국 그래프에서 사이클이 생기는 부분을 찾고, 그 부분에 해당하는 학생들의 수를 구해 n에서 빼면 되는 문제이다.
핵심 포인트는

1. 한번 방문한 학생은 다시 방문하지 않아야 한다는 것
2. 사이클을 어떻게 탐지할 것

이렇게 두 가지이다.

1) 한번 방문한 학생은 다시 방문하지 않아야 한다는 것

이 부분은 단순히 visited[]배열로 처리가능하다.
다만 한 번 방문했던 노드를 방문처리할 때 사이클이 생기지 않았어도 방문처리해야한다는 아이디어를 나중에 생각해서 꽤나 고생했다.
어차피 한 번 방문했을때 사이클을 발견하거나, 발견하지 못하는 경우 모두 나중에 방문할 이유가 없기에 모두 방문처리 해준다.

이 부분에서 계속 시간초과가 났었었는데, 한번 dfs를 돌 때마다 해당 dfs에서 방문한 노드를 체크하기 위해 생성하고 있었던 temp_visited[] 배열을 없애주고, 단순히 visited[]로만 처리해주니 문제를 해결할 수 있었다.

2) 사이클을 어떻게 탐지할 것

처음엔 단순히 사이클은

1. 자기 자신을 가리키거나
2. 아니면 현재 시작점으로 돌아오는 경우
   이 두가지밖에 생각하지 않았지만, 나중에 보니
3. 시작점이 사이클에 포함되진 않지만 중간에 사이클을 만나는 경우
   이렇게 총 3가지가 있었다.

큐와 visited[]배열을 이용해 사이클을 탐지해 주었으며, 만약 방문한 노드를 다시 방문했을 경우, 큐에서 해당 방문한 노드까지를 뺀다.
이렇게 되면 큐에 남아있는 부분은 사이클 부분만이 남게 된다.
큐가 빈 경우-모든 요소들이 제거된 경우는 사이클이 없다는 뜻이다.

추가로 생각해 볼만한 점, 배운 점

• fill()대신 memset()을 사용하면 좀 더 빠르게 배열을 초기화할 수 있다. 단, memset()은 -1, 0으로만 초기화가 가능하다는 점 주의.
• for문에서 매번 vector<>(n)만큼의 배열을 초기화(선언)해도 시간 초과가 날 수 있다.

코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define NUM 100000
using namespace std;

const bool debug = false;
bool visited[NUM] = {0};
int selection[NUM] = {0};

void check_group(int current, queue<int> &temp_queue);

// 241221 solved
int main() {
    fastio;
    int t;
    cin >> t;
    for(int tc = 0; tc < t; tc++){
        int n;
        cin >> n;

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

        // solving
        int ans = n;

        fill(visited, visited + n, 0);  // visited[] init
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                queue<int> temp_queue = {}; // temp_queue init
                check_group(i, temp_queue);
                // 사이클이 만들어진 경우 - 사이클의 크기만큼 ans에서 빼준다.
                ans -= temp_queue.size();
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

// dfs를 통해 사이클을 탐지해 큐에 저장하는 함수
void check_group(int current, queue<int> &temp_queue){
    int next = selection[current];
    temp_queue.push(current);
    visited[current] = true;
    // 다음 노드가 어떻게든 이미 방문되었다면
    if(visited[next]){
        // 방문된 노드를 큐의 최전방에 배치, 그 전에 방문했던 다른 노드들은 큐에서 모두 삭제.
        while(!temp_queue.empty() && temp_queue.front() != next){
            temp_queue.pop();
        }
        return;
    }
    // 다음 노드가 방문되지 않았다면 다음 노드로 이동
    check_group(next, temp_queue);
    return;
}