서로소집합 DisjointSet

각 원소가 집합을 이루게 하거나, 집합을 관리하기 위해 사용되는 자료구조

각 원소가 어떤 집합에 속하는지 빠르게 찾아내고 두개의 집합을 하나로 합치는 연산을 지원한다.

 

최소 신장트리 알고리즘, 사이클 감지에 유용하다.

DisjointSet에 각 원소를 추가시켜둔 상황이다.

처음은 집합을 설정하지 않았으므로 집합은 총 원소개로 구성된다.

 

집합을 만들어보자.

 

Union 메서드

Union(2,5)

2와 5를 하나의 집합으로 구성시킨다.

서로 각자를 대표하는 값중 어떤값이 더 작은지 확인하고, 큰값의 부모를 작은값으로 수정하는 등의 설정이 필요하다.

이로써 자신의 집합중 어떠한 값이 집합을 대표하는 값인지 바로 확인이 가능하다.

 

Union(3,5)

3과 5의 원소를 집합으로 구성시키려한다.

이때 각 대표값들을 확인해보면 3 = 3 , 5 = 2 이므로 3의 대표값을 5의 대표값으로 바꿔줘야한다.

 

Find 메서드의 경우 자신의 속한 대표값만 반환해주면 되므로 재귀를 활용해 쉽게 구현할수 있다.

 

class DisjointSet
{
    Dictionary<int,int> dic;

    public DisjointSet()
    {
        dic = new Dictionary<int, int>();
    }

    public void Add(int element)
    {
        if(!dic.ContainsKey(element))
            dic.Add(element,element);
    }

    public void Union(int x, int y)
    {
        if(!dic.ContainsKey(x))
            return;
        
        if(!dic.ContainsKey(y))
            return;

        x = Find(x);
        y = Find(y);

        int min = Math.Min(x,y);
        int max = Math.Max(x,y);

        dic[max] = min;
    }

    public int Find(int element)
    {
        if(!dic.ContainsKey(element))
            return int.MaxValue;

        if(dic[element] != element)
            dic[element] = Find(dic[element]);

        return dic[element];
    }
}

 

미흡한부분이나 개선될수 있는 부분이 있다면 답글 남겨주세요