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

풀이

크루스칼 알고리즘을 이용해 풀었다.

비용이 적게드는 순서대로 연결을 한다. 연결을 할때 circle이 생기는지 확인하고 생기지 않는다면 연결한다.
루트노드를 갱신시켜줄때 일반적으로 작은 노드를 루트노드로갱신시켜준다고한다.

(거꾸로 해도 되고 매번 다르게 해도 정답이나온다.  )

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

using namespace std;

int parent[101];
int getParent(int node){
    if(parent[node]==node) return node;
    return parent[node] = getParent(parent[node]);
}

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

int solution(int n, vector<vector<int>> costs) {
  int answer=0;
    for(int i=0;i<n;i++)
        parent[i]=i;
    
    sort(costs.begin(), costs.end(), cmp);

    
    for(int i=0;i<costs.size();i++){
        int from = getParent(costs[i][0]);
        int to = getParent(costs[i][1]);
        int cost = costs[i][2];
        
        if(from!=to){
            answer+=cost;
            if(from<to)
                parent[from]=to;
            else
                parent[to] =from;
        }
        
    }
    
    return answer;
}

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

union-find알고리즘 최적화하는 방법도 익혀두면 다른 알고리즘문제 풀때 도움될듯하다.