자료구조 - 서로소 집합

서로소 집합은 데이터를 여러 가지 집합으로 분리하는 자료구조로 각 데이터를 같거나 다른 집합으로 분리하여 집합 관계를 표현합니다. 서로소 집합 자료구조는 X가 속한 집합과, Y가 속한 집합을 합치는 UNION(X, Y) 연산과 X가 속한 집합을 찾는 FIND(X) 연산으로 구성되어 있으며, UNION-FIND 자료구조라 부르기도 합니다. 

각 집합은 루트 노드로 표현되며 UNION 연산은 각 데이터의 속한 집합이 다른 경우 합쳐주면서 루트 노드를 통일합니다. FIND 연산은 해당 데이터가 속한 집합의 루트 노드를 반환합니다.

여러 개의 합치기 연산이 주어졌을 때, 서로소 집합은 다음과 같이 동작합니다. 

• X가 속한 집합의 루트 노드와, Y가 속한 집합의 루트 노드를 확인합니다. 
• 같은 집합일 경우, 따로 합치기 연산을 수행할 필요가 없고 다른 집합일 경우 합치면서 합쳐지는 쪽의 루트를 변경합니다. 

EXAMPLE

1부터 6까지 존재하는 데이터에 대해 UNION(1,4), UNION(2,3), UNION(2,4), UNION(5,6) 의 4개의 합치기 연산에 대해 동작 과정을 한 번 살펴보겠습니다. 서로소 집합 연산은 각 데이터를 여러 집합으로 분리하고 각 집합마다 부모 노드를 표현하는 테이블이 필요합니다. 부모 노드를 타고 가면서 계속 확인하면 루트 노드를 알 수 있습니다.

1. STEP 1

맨 처음 부모 노드 테이블은 자기 자신으로 초기화합니다. 즉, 각 데이터 하나하나가 하나의 집합이 되는 것이죠.

데이터	1	2	3	4	5	6
부모 노드	1	2	3	4	5	6

 

2. STEP 2 

UNION(1,4) 연산입니다. 1이 속한 집합과 4가 속한 집합을 하나로 합칩니다. 이 때, 각 집합의 루트 노드를 하나로 합쳐 1과 4가 같은 집합에 속한다는 것을 표현해주어야 합니다. 루트 노드는 작은 값으로 정해보도록 하겠습니다.

데이터	1	2	3	4	5	6
부모 노드	1	2	3	1	5	6

 

3. STEP 3

UNION(2,3) 연산입니다. STEP 2에서처럼 2가 속한 집합과 3이 속한 집합을 하나로 합치고 3의 부모 노드를 2로 바꾸어줍니다.

데이터	1	2	3	4	5	6
부모 노드	1	2	2	1	5	6

 

4. STEP 4

UNION(2,4) 연산입니다. 2가 속한 집합 (2)과 4가 속한 집합 (1)이 다르니 이 둘을 합칩니다. 이 때, 2가 속한 집합의 루트 노드를 1로 바꾸어 줍니다.

데이터	1	2	3	4	5	6
부모 노드	1	1	2	1	5	6

 

5. STEP 5

마지막 UNION(5,6) 입니다. 5가 속한 집합과 6이 속한 집합을 합치면서 루트 노드 테이블을 업데이트합니다. 최종적으로는 루트 노드 1, 루트 노드 5를 가진 2개의 집합으로 데이터가 분리됩니다.

데이터	1	2	3	4	5	6
부모 노드	1	1	2	1	5	5

 

구현

경로 압축 (Path compression)

합치기 연산은 각 집합의 루트 노드를 찾아 같은지 다른지 비교해야 하며 부모 노드 테이블로 루트 노드를 바로 찾을 수 없고 부모 테이블을 지속적으로 확인해야 합니다. 이는 최악의 경우 루트 노드를 찾는 FIND 연산이 모든 데이터를 다 찾게 되어 시간 복잡도가 $O(V)$ ($V$는 데이터의 개수)가 되버리기 때문에 비효율적이지요.

FIND 연산을 효율적으로 수행하기 위해 FIND 연산을 재귀적으로 실행하면서 한 번 찾은 부모값을 계속 갱신시킵니다. 다이나믹 프로그래밍에서의 특정 부분 문제의 답을 테이블에 적어놔 값을 바로 읽을 수 있게 하는 것과 비슷한 이치입니다. UNION 연산을 다 수행한 후 각 원소에 대해 FIND 연산을 수행하면 부모 노드 테이블이 곧 루트 노드 테이블이 되므로 거의 $O(1)$에 FIND 연산이 가능해집니다.

파이썬 코드

def find_parents(parent, x): # parent는 초기화된 루트 노드 테이블
    ## 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
    	## 테이블에 루트 노드가 담기도록 업데이트
        parent[x] = find_parents(parent, parent[x])
        
    return parent[x]
    
def union(parent, a, b): # 합치기 연산
    ## a, b에 대한 루트 노드를 찾고
    parent_a = find_parents(parent, a)
    parent_b = find_parents(parent, b)
    ## 작은 루트 노드로 합치기
    if parent_a < parent_b:
        parent[parent_b] = parent_a
    else:
        parent[parent_a] = parent_b

 

무방향 그래프 사이클 판별

서로소 집합은 무방향 그래프에서의 사이클이 존재하는지를 판단하는데 사용할 수 있습니다. 참고로 방향 그래프에서의 사이클은 DFS를 이용합니다.

그럼 어떻게 사이클 존재 여부를 판단할까요?

1. 모든 노드에 대해 자기 자신을 부모로 가지는 테이블을 만듭니다.
2. 그래프는 정점과 정점을 잇는 간선 정보가 존재하는데, 각 간선에 대해서 간선이 잇는 두 정점에 대한 루트 노드를 확인합니다.
3. 루트 노드가 다를 경우 UNION 연산을 수행합니다. 루트 노드가 같을 경우 사이클이 존재한다고 판단합니다.

쉬운 이해를 위해 정점 1,2,3 을 잇는 간선 (1,2), (2,3), (1,3)이 존재한다고 가정해보면 이 그래프는 1,2,3 사이의 사이클이 존재합니다. 먼저, (1,2)에 대해 UNION 연산을 수행하면 1,2의 루트 노드가 다르므로 합쳐지면서 부모 노드가 갱신됩니다. (2,3)에 대해 UNION 연산을 수행하면 2,3의 루트 노드가 다르므로 합쳐지면서 부모 노드가 갱신됩니다. 마지막 (1,3)에 대해서 확인할 때, 1과 3의 루트 노드가 같으므로 (1,3)에 의해 사이클이 발생한다고 판단할 수 있는 것입니다.

파이썬 코드

def check_cycle(parent, 간선정보): # 무방향 그래프의 간선 정보가 들어왔을 때,
    cycle = False # 맨 처음 cycle이 없다고 가정
    for edge in 간선정보:
        a, b = edge
        ## edge를 구성하는 a, b에 대해 루트 노드 확인
        if find_parent(parent, a) == find_parent(parent, b): # 루트 노드가 같다면 사이클 존재
            cycle = True
            break
        else: # 다르다면 UNION 연산 수행
            union(a, b)
            
  	return cycle