[백준,c++] 18116번 - 로봇 조립

문제

18116번: 로봇 조립

 

코드

#include <iostream>
#include <vector>
using namespace std;


int N;
int parent[1000001];
int child_cnt[1000001];

int find_parent(int x){
    if(x == parent[x]) return x;
    else return parent[x] = find_parent(parent[x]);
    
}

void union_parent(int a, int b){
    a = find_parent(a);
    b = find_parent(b);
    
    if(a<b){
        parent[b] = a;
        child_cnt[a] += child_cnt[b];
        child_cnt[b] = 0;
    }
    else{
        parent[a] = b;
        child_cnt[b] += child_cnt[a];
        child_cnt[a] = 0;
    }
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    
    for(int i=1; i<1000001; i++){
        parent[i] = i;
        child_cnt[i] = 1;
    }
    
    for(int i=0; i<N; i++){
        char cmd; cin>>cmd;
        if(cmd == 'I'){
            int a, b; cin>>a>>b;
            if(find_parent(a) != find_parent(b)) union_parent(a, b);
        }
        else if(cmd == 'Q'){
            int a; cin>>a;
            cout<< child_cnt[find_parent(a)]<<'\n';
        }
    }
}

 

풀이

어떤 노드가 몇 개의 자식 노드를 가지는지 찾는 문제인 유니온 파인드 문제였습니다. 

자식 노드가 몇 개인지를 기록하는 배열을 생성해놓고 유니온 파인드를 통해서 부모 노드를 합칠 때, 해당 자식 노드를 갱신하는 아이디어로 풀이했습니다.

마지막 출력 부분에서  cout<< child_cnt[find_parent(a)]<<'\n'; 를 cout<< child_cnd[parent[a]]<<'\n';라고 처음에 작성했는데 틀렸다고 오답이 떠서 아직까지 왜 그런지는 잘 모르겠습니다.. 혹시나 아시는 분 계시면 댓글 남겨주시면 감사하겠습니다.