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

✅ LV.3

📌 Greedy

✏️ 최종 솔루션

⭐️ 크루스칼

1. 간선을 기준으로 오름차순 정렬
2. 모든 간선의 부모 노드를 자기 자신으로 초기화
3. 현재 간선의 두 노드의 부모 노드가 다르면 연결하고 가중치를 answer에 더하기
   1) 현재 노드의 부모노드를 DFS로 탐색해서 루트 노드를 return
   2) 두 부모 노드 중 값이 큰 부모 노드의 루트 노드를 작은 부모 노드 값으로 갱신

📌 self feedback

다익스트라 알고리즘과 달리 크루스칼 알고리즘에서는 부모 노드를 갱신해가며 탐색하는 것이 중요

🔗 크루스칼 알고리즘

✏️ 최종 code

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

using namespace std;

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

int getParent(int n) {
    if(parents[n]==n) return n;
    else return getParent(parents[n]);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;

    for(int i=0;i<n;i++) {
        parents.push_back(i);
    }
    
    sort(costs.begin(),costs.end(),cmp);
    
    for(int i=0;i<costs.size();i++) {
        int a=costs[i][0];
        int b=costs[i][1];
        int c=costs[i][2];
        
        int pa=getParent(a);
        int pb=getParent(b);
        
        if(pa!=pb) {
           if(pa<pb) parents[pb]=pa;
            else parents[pa]=pb;
            
            answer+=c;
        }
    }
    
    return answer;
}