Union Find에 관한 고찰 [프로그래머스] 네트워크

문제는 정말 간단히 링크들이 주어졌을 때, disjoint-set의 수를 출력하는 문제였다.
원래의 union은 부모노드끼리만 비교해서 작은 값을 부모노드로 교체해주면 되지만,
일반적으로 나는 자식노드도 최종부모로 바꿔준다. 이를 경로 압축이라고 흔히들 이야기한다.

void unionParent(int start, int end){
    int startParent = getParent(start);
    int endParent = getParent(end);
    int minParent = min(startParent, endParent);
    parent[startParent] = parent[endParent] = parent[start] = parent[end] = minParent;
}

중요한 건 이렇게 한다고 해서 무조건 parent[i] = i가 부모가 되지는 않는다.
union을 할때마다 해당하는 내 값, 부모값 만 업데이트 해주는 것일 뿐 연결된 다른 모든 노드들의 parent를 바꿔주지는 않으니까 말이다.

그러니까 경로압축을 했어도 모든 자식들의 부모를 찾을 때는
getParent(혹은 find) 함수로 부모를 찾아야 한다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
vector<int> parent;
vector<bool> isParentArr;

int getParent(int a){
    if(parent[a] == a) return a;
    else return(getParent(parent[a]));
}

void unionParent(int start, int end){
    int startParent = getParent(start);
    int endParent = getParent(end);
    int minParent = min(startParent, endParent);
    parent[startParent] = parent[endParent] = parent[start] = parent[end] = minParent;
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    parent.assign(n,0);
    isParentArr.assign(n,false);
    
    for(int i=0; i<n; i++){
        parent[i] = i;
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(computers[i][j]==1){
                unionParent(i,j);
            }
        }
    }
    
    for(int i=0; i<n; i++){
        if(!isParentArr[getParent(i)]){
            isParentArr[getParent(i)] = true;
            answer++;
        }
    }

    return answer;
    
}