[프로그래머스 LV3] - 섬 연결하기(kruskal) c++

문제

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

프로그래머스

접근방법

kruskal을 사용했다.

 

kruskal 알고리즘은 다음과 같이 구현한다.

 

그래프를 weight 오름차순으로 정렬하고,

weight가 작은 순서대로 edge를 추가한다.

 

이 때, edge의 각 vertice가 두 개의 sub set을

cross하는 지를 알아야한다.

 

만약, 같은 subset에 있다면,

그 edge는 MST(minimum spanning tree)에 포함되지 않는다.

 

코드

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

using namespace std;

struct p_r {
    int parent;
    int rank;
};

map<int, p_r> sub_sets;

int Find(int a) {
    if (sub_sets[a].parent == a) return a;
    return Find(sub_sets[a].parent);
}

void Union(int a, int b) {
    int aroot = Find(a);
    int broot = Find(b);
    
    if (sub_sets[aroot].rank < sub_sets[broot].rank) {
        sub_sets[aroot].parent = broot;
    } else if (sub_sets[aroot].rank > sub_sets[broot].rank) {
        sub_sets[broot].parent = aroot;
    } else {
        sub_sets[broot].rank++;
        sub_sets[aroot].parent = broot;
    }
}



int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    sort(costs.begin(), costs.end(), [](vector<int> a, vector<int> b) {
        return a[2] < b[2];
    });
    
    for (const auto& c : costs) {
        p_r a; a.parent = c[0]; a.rank = 0;
        p_r b; b.parent = c[1]; b.rank = 0;
        sub_sets[c[0]] = a;
        sub_sets[c[1]] = b;
    }
    
    //kruskal 알고리즘
    //weight가 작은 순서대로 넣으면서
    //vertice가 속한 subset이 다른 경우 이어줌.
    for (const auto& c : costs) {
        int a = Find(c[0]);
        int b = Find(c[1]);
        if (a != b) {
            Union(a, b);
            answer += c[2];
        }
    }
    
    
    return answer;
}

개선할 점

prim's algorithm도 알아보자.