[C++] 프로그래머스 : 섬 연결하기

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

using namespace std;

bool cmp(vector<int> node1, vector<int> node2){
    return node1[2] < node2[2];
}

int getParent(vector<int>& parent, int node){
    if(parent[node] == node)
        return node;
    return parent[node] = getParent(parent, parent[node]);
}

void unionParent(vector<int>& parent, int node1, int node2){
    int parent1 = getParent(parent, node1);
    int parent2 = getParent(parent, node2);
    if(parent1 < parent2){
        parent[parent2] = parent1;
    }else{
        parent[parent1] = parent2;
    }
    
}

int find(vector<int>& parent, int node1, int node2){
    int parent1 = getParent(parent, node1);
    int parent2 = getParent(parent, node2);
    if(parent1 == parent2)
        return 1; 
    else
        return 0;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int size = 0;
    
    sort(costs.begin(), costs.end(), cmp);
    
    // 부모노드를 담을 벡터
    // 값을 변화시켜 줘야하기 때문에 
    // 함수 인자로 전달시 & 사용해서 참조로 전달
    vector<int> parent;
    
    
    for(auto line: costs){
        if(size < line[1])
            size = line[1];
    }
    
    for(int i = 0; i <= size; i++){
        parent.push_back(i);
    }
    
    
    
    for(auto line: costs){
        if(!find(parent, line[0], line[1])){
            answer += line[2];
            unionParent(parent, line[0], line[1]);
        }
    }
    
    return answer;
}