Algorithm in A..Z - MST (Kruskal)

개념

MST란 Minimun Spanning Tree의 약어로 최소 신장트리를 뜻한다.

=> 신장트리 중에서 가중치의 합이 최소인 신장트리를 구하는 것

=> 신장트리 : Cycle이 없는 그래프

 

Kruskal

DisjointSet을 이용하여 MST를 갱신하며 구하는 알고리즘

---

작동원리

1. 모든 간선을 가중치 기준으로 오름차순으로 정렬한다.

2. 가중치가 작은 간선부터 확인하면서 간선에 속한 정점 v1, v2가 다른 SET이면 UNION하고 WEIGHT만큼 RESULT에 더한다.

---

시간복잡도

간선을 정렬 할 때 : O(ElogE)

DisjointSet 사용할 때 : O(1)

 

O(ElogE)

---

문제

16398 행성 연결

www.acmicpc.net/problem/16398

16398번: 행성 연결

---

코드

#include <bits/stdc++.h>
using namespace std;

class Edge {
public:
    int vertex1, vertex2, distance;

    Edge(int vertex1 = 0, int vertex2 = 0, int distance = 0) : vertex1(vertex1), vertex2(vertex2), distance(distance) {

    }

    bool operator<(const Edge &e) const {
        return distance < e.distance;
    }
};

class Disjoint {
    vector<long long> disjoint;

public:
    Disjoint(int n = 0) {
        disjoint.resize(n, -1L);
    }

    long long find(int index) {
        if (disjoint[index] < 0) {
            return index;
        }

        return disjoint[index] = find(disjoint[index]);
    }

    long long count(int v1) {
        return -disjoint[v1];
    }

    void unionSet(int v1, int v2) {
        if (v1 != v2) {
            disjoint[v1] += disjoint[v2];
            disjoint[v2] = v1;
        }
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> map(n, vector<int>(n));
    for (auto &ve : map) {
        for (auto &i : ve) {
            cin >> i;
        }
    }

    vector<Edge> edges(n);
    for (int i = 0;i < n;++i) {
        for (int j = 0;j < n;++j) {
            if (i == j) {
                continue;
            }

            edges.emplace_back(i, j, map[i][j]);
        }
    }

    long long ans = 0L;
    Disjoint disjoint(n);
    sort(edges.begin(), edges.end());
    for (auto &edge : edges) {
        int v1 = disjoint.find(edge.vertex1);
        int v2 = disjoint.find(edge.vertex2);

        if (v1 != v2) {
            ans += edge.distance;
            disjoint.unionSet(v1, v2);
        }
    }

    cout << ans << "\n";
}