백준 16202번 MST게임(C++)🚩

문제가 이해안되서 잘못 풀었는데 

정점은 고정되어있고 턴마다 간선이 줄어드는것이다. 처음엔 간선들 사이에 여러개 트리가 있나? 했는데 그게 아니라 

간선이 줄어드면서 똑같이 n개의 정점에 대하여 트리가 되는지 푸는 문제이다. 

거기다 처음에 find()함수에 리턴을 = 이아니라 <로 해서 계속 안되서 어이없었다..

 

런타임에러

아직 왜 나는지 모르겠다. 아마 무한루프가 나는것 같은데.. 65%에서 난다.

 

#include<vector>
#include <iostream>
#include<queue>
#include<tuple>
#include<set>

using namespace std;

typedef tuple<int,int,int> tp;

vector<int>parent;

int find(int node){
    if(parent[node]<0)return node;
    
    return parent[node]=find(parent[node]); //하...
}

bool unions(int x,int y){
    
    int xp=find(x);
    int yp=find(y);
    
    if(xp==yp)return false;
    
    if(parent[xp]<parent[yp]){
        parent[xp]+=parent[yp];
        parent[yp]=xp;
    }
    else{
        parent[yp]+=parent[xp];
        parent[xp]=yp;
    }
    return true; 
}


int main()
{
    int n,m,k;
    cin>>n>>m>>k; 
    parent.assign(n+2,-1);
    
    vector<vector<bool>>visited;
    visited.assign(n+2,vector<bool>(n+2,false)); //간선 없애기 
    
    vector<tp>pq; 
    
    int x,y;
    for(int i=1;i<=m;i++){
        cin>>x>>y; 
        pq.push_back({i,x,y}); 
        visited[x][y]=true;
    }
    
    vector<int>ans(k,0);
    
    int turn=0;
    
    //정점을 모두 사용한 트리군 트리가 되기만하면 되는게 아니라 
    //트리가 작게 여러개인줄 
    
    //런타임에러 왜나 
 
    while(1){
        
        int mins=10000000;     
        int sum=0;
        int cnt=0; 
        int x1,y1;   
        int first=0;
        
        parent.assign(n+1,-1);//이거!!!!!!!!!!!!!!
        
        //
        
        for(int i=0;i<pq.size();i++){
     
            int w=get<0>(pq[i]);
            int a=get<1>(pq[i]);
            int b=get<2>(pq[i]);
            
            
            if(!visited[a][b])continue; 
            
            first++;
            
            if(first==1){
                x1=a; y1=b; 
               
            }
            
            if(unions(a,b)){
                sum+=w; 
                cnt++; 
                
            }
        }        
   
        
        if(cnt==n-1){ //이거였음..? 
            ans[turn]=sum;
            turn++; 
            //제일 작은 간선 못쓰게함 
            visited[x1][y1]=false; 
            
        }
        else break;
        
    }
    
   for(int i=0;i<k;i++)cout<<ans[i]<<' ';
   
   return 0; 

    
}

 

정답

#include<vector>
#include <iostream>
#include<queue>
#include<tuple>
#include<set>

using namespace std;

typedef tuple<int,int,int> tp;

vector<int>parent;

int find(int node){
    if(parent[node]<0)return node;
    
    return parent[node]=find(parent[node]); 
}

bool unions(int x,int y){
    
    int xp=find(x);
    int yp=find(y);
    
    if(xp==yp)return false;
    
    if(parent[xp]<parent[yp]){
        parent[xp]+=parent[yp];
        parent[yp]=xp;
    }
    else{
        parent[yp]+=parent[xp];
        parent[xp]=yp;
    }
    return true; 
}


int main()
{
    int n,m,k;
    
    cin>>n>>m>>k; 
    
    parent.assign(n+2,-1);
    
    vector<vector<bool>>visited;
    visited.assign(n+2,vector<bool>(n+2,false)); //간선 없애기 
    
    vector<tp>pq; 
    
    int x,y;
    for(int i=1;i<=m;i++){
        cin>>x>>y; 
        pq.push_back({i,x,y}); 
        visited[x][y]=true;
    }
    
    vector<int>ans(k,0);
    
    int turn=0;
    
    //정점을 모두 사용한 트리 트리가 되기만하면 되는게 아니라 
    //트리가 작게 여러개인줄 
   
 
    for(int j=0;j<k;j++){
        
        int sum=0;
        int cnt=0; 
        
        parent.assign(n+1,-1);//이거!!!!!!!!!!!!!!
       
        for(int i=j;i<pq.size();i++){
     
            int w=get<0>(pq[i]);
            int a=get<1>(pq[i]);
            int b=get<2>(pq[i]);
            
            
            if(!visited[a][b])continue; 
            
            if(unions(a,b)){
                sum+=w; 
                cnt++; 
                
            }
        }        
   
        
        if(cnt==(n-1)){ 
            ans[j]=sum;
        
            //제일 작은 간선 못쓰게함 
            visited[get<1>(pq[j])][get<2>(pq[j])]=false; 
           
        }
        
        
    }
    
   for(int i=0;i<k;i++)cout<<ans[i]<<' ';
   
   return 0; 

    
}