프로그래머스 섬 연결하기 c++ // 크러스칼 알고리즘

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

프로그래머스

1. 특이한 부분 재귀함수

//부모노드찾기
int get_parent(int node){
    if(parent[node]==node) return node;
    return parent[node]=get_parent(parent[node]);
}

2. 합집합

 

//같은집합으로 만드는함수
void union_parent(int node1, int node2){
    int p1=get_parent(node1);
    int p2=get_parent(node2);
    
    //노드숫자가 작은쪽으로 병합
    //node1의 루트노드를 node2의 루트노드에 연결!!!
    if(p1>p2){
        parent[p1]=p2;
    }
    else{
        parent[p2]=p1;
    }
}

우측 4-5에서

5의 루트노트(4)의 부모를 노드3의 루트노드로 바꾸면 합집합이 구현된다!

 

#include <bits/stdc++.h>

using namespace std;

int parent[104];

//부모노드찾기
int get_parent(int node){
    if(parent[node]==node) return node;
    return parent[node]=get_parent(parent[node]);
}

//같은그룹인지 검사
int find(int node1, int node2){
    if(get_parent(node1)==get_parent(node2)){
        return 1;
    }    
    return 0;
}

//같은집합으로 만드는함수
void union_parent(int node1, int node2){
    int p1=get_parent(node1);
    int p2=get_parent(node2);
    
    //노드숫자가 작은쪽으로 병합
    //node1의 루트노드를 node2의 루트노드에 연결!!!
    if(p1>p2){
        parent[p1]=p2;
    }
    else{
        parent[p2]=p1;
    }
}

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

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    sort(costs.begin(),costs.end(),cmp);    
    
    //초기값 : 자기자신을 부모로 두기
    for(int i=0;i<n;++i){
        parent[i]=i;
    }
    
    int edge_count=0;
    for(auto v:costs){
        if(find(v[0],v[1])) continue;   //같은그룹이면 == 연결시 사이클을 만들면 pass
        union_parent(v[0],v[1]);
        answer+=v[2];
        
        
    }
    
    return answer;
}