텀 프로젝트

정말 많이 틀린 DFS문제다.

#include<iostream>
#include<vector>
#include<cstring>
 
 
using namespace std;
 
int tc,n,ans;
 
 
void go(int x, int start, int team, vector<int>&v, vector<int>&memb,vector<bool>&g){
    if(memb[x] == start){
        ans -= team;
        return;
    }
    else{
        int y = memb[x];
        if(g[y] == false){
            v.push_back(y);
            g[y] = true;
            go(y, start, team+1,v,memb,g);
            v.pop_back();
        }
        else{
            for(int i = 0; i < v.size(); i++){
                g[v[i]] = false;
            }
            return;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>tc;
    for(int t = 1; t<= tc; t++){
        cin>>n;
        ans = n;
        vector<bool> g(n+1);
        vector<int> memb(n+1);
        memb.push_back(0);
        for(int i = 1; i <= n; i++){
            g[i] = false;
            cin>>memb[i];
        }
        for(int i = 1; i<= n; i++){
            if(g[i] == false) {
                vector<int> v;
                go(i, i, 1, v, memb,g);
            }
        }
        cout<<ans<<'\n';
 
 
 
    }
}

Bool을 벡터형태로짜든, 배열에서 초기화를하든 82%대에서 계속해서 시간초과가 났다.

원인을 계속해서 분석을계속해서 해본결과 딱하나의 문제점을 발견했다.

 

처음 위와 같이 짠 알고리즘의 가장큰 문제점은 끝까지 돌지 못했을때 처음시작하는 체크포인트를 체크하지않는다는것이다.

 

 

#include<iostream>
#include<vector>
#include<cstring>
 
 
using namespace std;
 
int tc,n,ans;
 
 
void go(int x, int start, int team, vector<int>&v, vector<int>&memb,vector<bool>&g){
    if(memb[x] == start){
        ans -= team;
        return;
    }
    else{
        int y = memb[x];
        if(g[y] == false){
            v.push_back(y);
            g[y] = true;
            go(y, start, team+1,v,memb,g);
            v.pop_back();
        }
        else{
            for(int i = 0; i < v.size(); i++){
                g[v[i]] = false;
            }
            return;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>tc;
    for(int t = 1; t<= tc; t++){
        cin>>n;
        ans = n;
        vector<bool> g(n+1);
        vector<int> memb(n+1);
        memb.push_back(0);
        for(int i = 1; i <= n; i++){
            g[i] = false;
            cin>>memb[i];
        }
        for(int i = 1; i<= n; i++){
            if(g[i] == false) {
                vector<int> v;
                g[i] = true;
                go(i, i, 1, v, memb,g);
            }
        }
        cout<<ans<<'\n';
 
 
 
    }
}

위와 같이 g[i]를 true로 놓고 탐색한 결과

시간초과를 해결할수있었다.