프로그래머스 (Programmers) 섬 연결하기

크루스칼로 풀었다.

/**

실수:

disjoint함수의 두 a,b값이 다른 경우 uf[disjoint(a)] = disjoint(b); 최상위 번호를 찾아 넣어줘야하는데...

uf[a] = disjoint(b) 로 넣어주었다.. ㅠㅠ

이렇게 되면 두집합이 합쳐질때 최상위번호가 바뀌는게 아니라.. 중간쯔음에서 바뀌기 때문에... 집합 전체가 합쳐지지 않는다.

오히려 이건 가능하다.

uf[disjoint(a)] = b

b는 최상위가 아니여도... a의 최상위를 b로 바꿔주었기때문에.. disjoint 함수를 부르게되면 최상위 번호로 갱신된다.

**/

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const vector<int>& a, const vector<int>& b) {
    return a[2] < b[2];
}
int uf[100];
int disjoint(int x) {
    if (uf[x] == x) return x;
    return uf[x] = disjoint(uf[x]);
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for (int i = 0; i < n; i++) {
        uf[i] = i;
    }
 
    int row = costs.size();
 
    sort(costs.begin(), costs.end(), &cmp);
 
    for (int i = 0; i < row; i++) {
        int a = costs[i][0];
        int b = costs[i][1];
        int cost = costs[i][2];
        if (disjoint(a) != disjoint(b)) {
            uf[disjoint(a)] = disjoint(b);
            answer += cost;
        }
        else {
            continue;
        }
    }
 
    return answer;
}