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

Kruskal 알고리즘은 간선들을 비용이 적은 순으로 모두 소팅한다음에,
cycle이 없는 경우에 한정해서 연결하면서 최소신장트리를 완성해나가는 것이다.
cycle이 없는 것을 판단하기 위해 기본적으로 union-find 작업을 잘 해야 한다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

vector<int> parentList;

class Edge {
public:
    int start;
    int end;
    int dist;

    Edge(int start, int end, int dist) {
        this->start = start;
        this->end = end;
        this->dist = dist;
    }

    bool operator <(const Edge &e) const {
        return this->dist > e.dist;
    }
};


int findParent(int a) {
    if (parentList[a] == a) {
        return a;

    }
    return parentList[a] = findParent(parentList[a]);
}

void unionParent(int a, int b) {
    parentList[findParent(a)] = parentList[findParent(b)] = min(findParent(a), findParent(b));
}


int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int cnt = 0;

    //parent 배열 초기화
    for (int i = 0; i < n; i++) {
        parentList.push_back(i);
    }

    priority_queue<Edge> pq;

    for (auto vec : costs) {
        pq.push(Edge(vec[0], vec[1], vec[2]));
    }

    while (!pq.empty()) {
        if(cnt==n) break;

        Edge curEdge = pq.top();
        pq.pop();
        int start = curEdge.start;
        int end = curEdge.end;
        if (findParent(start) == findParent(end)){
            continue;
        }
        answer += curEdge.dist;
        cnt++;
        unionParent(start, end);

    }

    return answer;
}

union-find를 할 때 제일 주의할 점은
a,b를 union할 때 결론적으로는 a,b의 parent를 union 해야 한다는 것이다.
즉, a,b의 parent를 a,b의 parent 중 더 작은 값으로 바꿔줘야 한다는 것이다.