프로그래머스 - 섬 연결하기

 

 

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

using namespace std;

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

int Find(vector<int>& parent, int x)
{
    if(parent[x] != x)
    {
        parent[x] = Find(parent, parent[x]);
    }
    return parent[x];
}

void Union(vector<int>& parent, vector<int>& rank, int x, int y)
{
    int node1 = Find(parent, x);
    int node2 = Find(parent, y);
    
    if(node1 != node2)
    {
        if(rank[node1] > rank[node2])
        {
            parent[node2] = node1;
        }
        else if (rank[node1] < rank[node2])
        {
            parent[node1] = node2;
        }
        else
        {
            parent[node2] = node1;
            rank[node1]++;
        }
    }
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    sort(costs.begin(), costs.end(), Compare);
    
    vector<int> parent(n);
    vector<int> rank(n,0);
    
    for(int i =0; i < n; ++i)
    {
        parent[i] = i;
    }
    
    int inEdge = 0;
    
    for (const auto& cost : costs) {
        int u = cost[0];  
        int v = cost[1];  
        int bridgeCost = cost[2];  
        
        
        if (Find(parent, u) != Find(parent, v)) {
            Union(parent, rank, u, v); 
            answer += bridgeCost;
            inEdge++;  
            
            
            if (inEdge == n - 1) {
                break;
            }
        }
    }
    
    
    
    return answer;
}