[백준]텀 프로젝트

이 문제를 올릴까 많이 고민했는데 결국 내 힘으로 다 못 풀고 남은 문제다. 문제가 좀 어렵고 알고리즘을 잘 모른다면 헷갈리는 부분이 훨씬 많아서 알고리즘 스터디를 더 하고 나서 다시 한번 도전해보고 싶은 그런 문제이다.

이 문제는 Cycle detection 이 포함되는 문제로 일반적인 그래프 탐색도 중요하지만 중복 체크와 함께 계산을 줄이는것에 초점을 맞춰야한다.

한 학생은 단 하나의 학생을 선택할 수 있고 그 학생들을 그래프 탐색해서 다시 돌아오게 된다면은 cycle 이 만들어졌기때문에 그룹을 뺀 나머지 사람들의 숫자를 출력하면 되는 문제다.

각 노드를 탐색하면서 visited 배열로 방문 확인을 해주는게 중요하다. 그리고 만약에 노드가 이미 방문된 노드를 방문할 경우, 그 노드가 이미 팀을 이루고 있는지에 대한 확인도 중요하다.

노드를 역추적 할 수 있는 방법으로 for 룹을 사용하며 역추적 할 수 있다는 새로운 방식을 배운거 같다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int answer,cnt; 
bool visited[100001]; 
int dp[100001]; 

void dfs(int student, vector<vector<int>>& adj){

    visited[student] = true;
    for(int& n : adj[student]){
        if(!visited[n]){
            dfs(n,adj); 
        }
        if(visited[n] && dp[n] == -1){
            for(int next = n; next != student; next = adj[next][0]){
                cnt++; 
            }
            cnt++; 
        }
    }
    dp[student] = student; 
}

void Solution(){
    int N; 
    cin >> N; 
    while(N--){
        int size; 
        cin >> size;
        vector<vector<int>> adj(size+1); 
        answer = size; 
        cnt = 0; 
        memset(visited,false,sizeof(visited)); 
        memset(dp,-1,sizeof(dp)); 
        for(int i = 1; i <= size; i++){
            int student; 
            cin >> student;
            adj[i].push_back(student); 
        }

        for(int i = 1; i <= size; i++){
            if(!visited[i]) dfs(i,adj); 
        }

        cout << answer - cnt << endl; 
    }
}


void Solve(){
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}