[프로그래머스] level 3 - 섬 연결하기, C++

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

코딩테스트 연습 - 섬 연결하기 | 프로그래머스

 본 문제는 n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만드는 문제다. 최소비용이므로 최소 스패닝 트리를 구현하면 된다. union-find를 사용하여 kruskal algorithm을 구현하여 풀었다.

#include <string>
#include <vector>
#include <tuple>
#include <algorithm>
 
using namespace std;
 
vector<tuple<int, int, int>> v;
int parent[101];
int Rank[101] = { 0 };
 
bool cmp(tuple<int, int, int> x, tuple<int, int, int> y) {
    int x1, x2, x3;
    int y1, y2, y3;
    tie(x1, x2, x3) = x;
    tie(y1, y2, y3) = y;
    return x3 < y3;
}
 
int Find(int x) {
    if (x == parent[x]) return x;
    else return parent[x] = Find(parent[x]);
}
 
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    if (Rank[x] < Rank[y]) swap(x, y);
    parent[y] = x;
    if (Rank[x] == Rank[y]) Rank[x] += 1;
}
 
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < costs.size(); i++) {
        v.push_back(make_tuple(costs[i][0], costs[i][1], costs[i][2]));
    }
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++) {
        int x, y, z;
        tie(x, y, z) = v[i];
        x = Find(x);
        y = Find(y);
        if (x != y) {
            Union(x, y);
            answer += z;
        }
    }
    return answer;
}