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

programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

 최소신장트리를 확인할 수 있는 알고리즘을 사용하여야 한다.  크루스칼 알고리즘을 사용하여 풀었다. GeeksForGeeks의 코드는 복잡해서 www.programiz.com/dsa/kruskal-algorithm를 참고했다.

int find_Root(vector<int> &root, int i){
    if(root.at(i)==i){
        return i;
    }
    return find_Root(root, root.at(i));
}
bool compare(vector<int> a, vector<int> b){
    return a.at(2) < b.at(2);
}
int solution(int n, vector<vector<int>> costs) {
    sort(costs.begin(), costs.end(), compare);
    
    vector<int> root;
    // 자기 자신을 root로 할당
    for(int i=0; i<n; ++i){
        root.push_back(i);
    }
    
    int answer = 0;
    for(vector<int> v:costs){
    	// 자기 자신을 가르키고 있으면 루트이다.
        // 루트를 찾는다.
        int u_root = find_Root(root,v.at(0));
        int v_root = find_Root(root,v.at(1));
        
        if(u_root!=v_root){
        	// 루트가 서로 다르면 합 하고
            root[v_root] = root[u_root];
            // cost를 늘린다.
            answer += v.at(2);
        }
    }
    return answer;
}