고오급 알고리즘을 공부하는 이유?

선구자들의 지혜를 배우고, 내가 보는 시야를 넓힌다.

최소 스패닝 트리 (Minimum Spanning Tree)를 공부를 할 것인데,

Minimum Spanning Tree => 그래프/트리의 활용정도가 된다.

이것을 알기전에 알고가야할 부분이

"상호 배타적 집합 (Disjoint Set)"이다.

https://www.youtube.com/watch?v=fNHLKhzEmVg

DSU라고도 한다.

Astar에서 가장 좋은 후보를 찾을 때 우선순위 큐를 사용을 하면 완전 찰떡궁합이였었다.

이와 비슷하게

최소 스패닝 트리를 사용을 할 대, Disjoint Set이 우선순위 큐처럼 최소 스패닝 트리의 좋은 부품 처럼 쓰이기에 얘부터 알아볼 것이다.

부르는 이름은 Disjoint set || Union Find(합치기 - 찾기)

이론

그냥 리니지 식으로 혈맹을 해서 싸울 경우

팀끼리 합병할 경우 이 알고리즘을 사용을 하는데...

아직 잘 모르겠다..

C++ 코드

class DisjointSet
{
public:
    DisjointSet(int n) : _parent(n), _rank(n, 1) 
    // std::vector's size => n
    {
        for (int i = 0; i < n; ++i)
        {
            _parent[i] = i;
        }
    }

    // 조직 폭력배 구조?
    // [1]		[3]
    // [2]	 [4][5][0]
    // 	

    // 니 대장이 누구니?
    int Find(int u)
    {
        if (u == _parent[u])
            return u;

        // _parent[u] = Find(_parent[u]);
        // return _parent[u];

        return _parent[u] = Find(_parent[u]);
    }

    // u와 v를 합친다 (일단 u가 v 밑으로)
    void Merge(int u, int v)
    {
        u = Find(u);
        v = Find(v);

        if (u == v)
            return;
        
        if (_rank[u] > _rank[v])
            std::swap(u, v);

        // rank[u] <= rank[v] 보장됨
        _parent[u] = v;
        
        if (_rank[u] == _rank[v])
            ++_rank[v];
    }

private:
    std::vector<int> _parent;
    std::vector<int> _rank;
};