[Algorithm] Union-Find(합집합 찾기)

※ Union-Find (합집합 찾기)

: 대표적인 그래프 알고리즘으로, 서로소 집합 알고리즘이라고도 한다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

 

 

 

위와 같이 여러 개의 노드가 존재한다. 모두 연결되어 있지 않고, 각자 자기 자신만을 집합의 원소로 가지고 있을 때 모든 값이 자기 자신을 가리키도록 표현할 수 있다.

 

0	1	2	3	4	5	6	7
0	1	2	3	4	5	6	7

 

이때, 0과 1이 연결되었다고 해보자. 그러면 1의 인덱스 값에 '0'이 들어간다. 일반적으로 합칠 때에는 더 작은 값 쪽으로 합치고, 이를 합침(Union)이라고 한다.

 

 

 

 

0	1	2	3	4	5	6	7
0	0	2	3	4	5	6	7

 

1와 2이 연결된 경우는 어떨까?

 

 

 

0	1	2	3	4	5	6	7
0	0	1	3	4	5	6	7

 

여기서 0과 2가 연결 되어 있는지 파악하는 것이 중요하다. 이때 사용되는 것이 재귀함수이다. 2의 부모를 찾기 위해 먼저 2가 가리키고 있는 1을 찾는다. 그러면 1의 부모가 0을 가리키고 있으므로 결과적으로 2의 부모가 1이라는 것을 파악할 수 있다. 

 

0	1	2	3	4	5	6	7
0	0	0	3	4	5	6	7

 

Find 알고리즘은 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인한다.

 

Union-Find 알고리즘을 Python 코드로 구현한 것은 다음과 같다.

 

[Python Code 👩🏻‍💻]

data_set = [i for i in range(8)]

def getparent(data_set,a):
    if(data_set[a]==a):
        return a
    return getparent(data_set,data_set[a])

def unionparent(data_set,a,b):
    a = getparent(data_set,a)
    b = getparent(data_set,b)
    if(a<b):
        data_set[b] = a
    else:
        data_set[a] = bx
        
        
def findparent(data_set,a,b):
    a = getparent(data_set,a)
    b = getparent(data_set,b)
    if(a==b):
        return 1
    return 0

unionparent(data_set,0,1)
unionparent(data_set,1,2)
unionparent(data_set,2,3)
unionparent(data_set,1,4)
unionparent(data_set,5,6)
unionparent(data_set,6,7)

print("1과 3는 연결되어 있습니까?",findparent(data_set,1,3))
print("1과 5는 연결되어 있습니까?",findparent(data_set,1,5))

위 코드를 바탕으로 그래프를 도식화하면 다음과 같다.

[결과]

그림과 같이 1과 3은 같은 집합에 속하므로 1을 return 한다.

1과 5는 다른 집합에 속하므로 0을 return 한다.

 

 

 

만약 1과 6을 연결한다면 결국 1과 5도 같은 집합에 속하게 된다.

unionparent(data_set,1,6)
print("1과 5는 연결되어 있습니까?",findparent(data_set,1,5))

 

Union-Find 알고리즘은 다른 고급 그래프 알고리즘의 베이스가 된다.