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

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

이 문제는 그리디 알고리즘의 일종인 크루스칼 알고리즘으로 풀었다.

크루스칼 알고리즘은 전에도 적었지만 가중치가 최소인 최소 스패닝 트리를 구할 때 사용하는 알고리즘이다.

해결 방법은

1. 간선을 벡터에 넣어주고 가중치가 낮은 순서로 정렬해준다.
2. parent 배열을 자기자신으로 지정한다.
3. 간선의 가중치가 낮은 순서부터 선택한다. 이때, 부모가 같으면 싸이클이 생기므로 부모가 다른지 확인해준다.
4. 가중치를 더하고, 각 정점의 parent를 같게 해준다.
5. 3~4를 반복한다.

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

using namespace std;

struct edge {
    int node[2];
    int value;
    edge(int a, int b, int c){
        this->node[0] = a;
        this->node[1] = b;
        value = c;
    }
    bool operator<(edge &a){
        return this->value < a.value;
    }
};

vector<edge> e;
int parent[101];

int find_parent(int n){
    if(parent[n] == n) return n;
    else return find_parent(parent[n]);
}

void union_parent(int a, int b){
    a = find_parent(a);
    b = find_parent(b);
    if(a < b)
        parent[b] = a;
    else 
        parent[a] = b;
}

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

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for(int i = 0; i < costs.size(); i++)
        e.push_back(edge(costs[i][0],costs[i][1],costs[i][2]));
    sort(e.begin(), e.end());
    for(int i = 0; i < n; i++){
        parent[i] = i;
    }
    
    for(int i = 0; i < e.size(); i++){
        if(find(e[i].node[0], e[i].node[1])){
            answer += e[i].value;
            union_parent(e[i].node[0], e[i].node[1]);
        }
    }
    
    return answer;
}