[그래프(크루스칼)] 프로그래머스 섬 연결하기 C++

 

https://programmers.co.kr/learn/courses/30/lessons/42861?language=cpp 

코딩테스트 연습 - 섬 연결하기

 

※ 크루스칼 알고리즘이란?

최소 신장 트리를 구하는 대표적인 알고리즘

 

* 최소 신장 트리 : 가중치 그래프에서 모든 정점을 포함하고 간선들의 가중치 합이 최소이며 사이클이 없는 트리

 

Union-Find로 구현

사이클 확인

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

using namespace std;

int parent[101];

int getRoot(int x) {
    if (x == parent[x]) return x;
    return parent[x] = getRoot(parent[x]);
}

void unions(int x, int y) {
    x = getRoot(x);
    y = getRoot(y);
    
    // x!=y (x)
    if (x<y) parent[y] = x;
    else if (x>y) parent[x] = y;
}

bool find(int a, int b) {
    a = getRoot(a);
    b = getRoot(b);
    if (a==b) return true;
    return false;
}

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

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    // 간선 비용으로 오름차순 정렬(간선 선택)
    sort(costs.begin(), costs.end(), cmp);
    
    // parent 초기화
    for(int i=0; i<n; i++) {
        parent[i] = i;
    }
    
    // 전체 정점 중 간선 비용이 작은 순으로 같은 부모를 가지고 있지 않으면 연결
    for(int i=0; i<costs.size(); i++) {
        if(!find(costs[i][0], costs[i][1])) {
            unions(costs[i][0], costs[i][1]);
            answer += costs[i][2];
        }
    }
    
    return answer;
}