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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42861

풀이

⭐대표적인 Union-Find 문제 | MST(크루스칼 알고리즘)

틀린 이유
1. 그리디라고 생각하면 적당한 알고리즘이 안 떠오름.. 많이 풀어보기✨
2. sort에서 정렬 기준 만들어주는 함수는 bool형
3. Find 함수에서 if else 각각 return 해줘야하는데 실수 함 ;;
4. 사이클이 생성되지 않을 때만 union하고 ans에 cost를 추가해줘야하는데 ans가 solution 함수에서 return되야하므로 main에서 바로 union 코드 작성하기

코드

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

using namespace std;

vector<int> root;

bool compare(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}

int Find(int node) {
    if(root[node] == node)
        return node;
    else
        return root[node] = Find(root[node]);
}

int solution(int n, vector<vector<int>> costs) {
    int ans = 0;
    
    for(int i=0; i<n; i++) {
        root.push_back(i);
    }
    
    sort(costs.begin(), costs.end(), compare);
    
    for(int i=0; i<costs.size(); i++) {
        int parent_a = Find(costs[i][0]);
        int parent_b = Find(costs[i][1]);
    
        if(parent_a != parent_b) {
            root[parent_b] = parent_a;
            ans += costs[i][2];
        }
    }
    
    return ans;
}