프로그래머스 : 섬 연결하기

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

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

 

크루스칼 알고리즘을 이용하였습니다.

각 간선들을 cost 오름차순으로 정렬한 뒤, 사이클이 없다면 연결시켜주는 방식으로 진행하였습니다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> d;

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

int getParent(int x) {
    if(d[x] == x) return x;
    return d[x] = getParent(d[x]);
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    d.resize(n);
    for(int i=0; i<n;i++) {
        d[i] = i;
    }
    sort(costs.begin(), costs.end(), compare); // 정렬
    for(int i=0; i<costs.size(); i++) {
        int cur1 = getParent(costs[i][0]);
        int cur2 = getParent(costs[i][1]);
        int cost = costs[i][2];
        if(cur1 != cur2) {
            if(cur1 < cur2) d[cur2] = cur1;
            else d[cur1] = cur2;
            answer += cost;
        }
    }
    return answer;
}