백준(boj)9466 - 텀 프로젝트

문제 링크 - https://www.acmicpc.net/problem/9466

👀문제이해 및 풀이방법

dfs 문제중 어려운 문제였다 solved.ac 난이도는 골드4 였지만 체감 난이도가 훨신 높았던것 같다

기본적으로 그래프에서 사이클을 찾는 문제이다.

알것같으면서도 잘 안되었는데 가장 중요한 것은 scc알고리즘과 달리 사이클을 분류해서 찾되 자기자신 혼자 사이클이 되는경우와 그냥 혼자 동떨어져 있는경우를 나눠야 한다는 것이다.

처음 시도는 기본적인 dfs 틀로 모든 정점을 하나하나 사이클이 되는지 찾아보았다.

바로 시간초과가 떳고 한번에 여러가지 정보를 분류해야겟다는 생각으로 한정점에서 dfs를 돌때 visit배열을 선언하여 이를 한번 더 만나면 그 이후 애들을 모두 사이클로 만드는 방식을 사용하였지만 또 시간초과였다

한번 dfs를 돌때 사이클인 정점들과 또 사이클이 아닌 정점들을 구분해서 앞으로의 dfs를 수행할 정점을 빼줘야 하는 것인데 왜인지 모르게 계속 시간초과가 났다.

결국 고민끝에 다른 글을 참고하여 풀어냈다 .. stack을 사용하는 dfs로는 힘든것 같았다 재귀형식의 dfs를 사용해야하는데 많이 사용을 안해봐서 생각해내기 힘들었던것 같다 앞으로 재귀형식의 dfs문제들을 조금 더 풀어봐야 겠다

📝코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class term_project{
private:
    vector<int> connect;
    vector<bool> visit,done;
    int N;
    int cnt=0;
public:
    term_project(){
        std::cin >> N;
        done.resize(N+1,false);
        visit.resize(N+1,false);
        connect.resize(N+1);
        set_val();
    }
    void set_val(){
        for(int i=1;i<=N;i++)
            std::cin >> connect[i];
    }
    void dfs(int a){
        visit[a]=true;
        
        int next = connect[a];
        if(!visit[next])
            dfs(next);
        else if(!done[next]){
            for(int i=next; i!=a;i=connect[i])
                cnt++;
            cnt++;
        }
        done[a]=true;
    }
    void find_sol(){
        for(int i=1;i<=N;i++)
            if(!visit[i])
                dfs(i);
        std::cout << N-cnt<<'\n';
    }
};
int main(){
    int n;
    std::cin >> n;
    for(int i=0;i<n;i++){
        term_project tp;
        tp.find_sol();
    }
    return 0;
}