Union Find 자료구조 이론

Union Find 자료구조 ( 서로소 집합 자료구조 )

 

서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

 

여기서 집합은 트리구조를 의미하고,

서로소 부분 집합은 루트노드가 다른 것을 의미한다.

 

그래서,

 

Union 

각자 서로소인 부분 집합을 하나의 집합으로 합치는 연산.

ex) union(1, 4) 이면 1의 루트노드와 4의 루트노드를 비교해서 더 큰 루트노드의 부모를 작은 루트노드로 세팅한다.

주의 : 해당 노드가 아닌 루트노드의 부모를 세팅하는 것이다.

 

Find 

어떤 원소가 어떤 집합에 속해있는지 (루트노드가 무엇인지) 알려주는 연산

ex) 루트를 찾을 때 까지 (부모가 자기자신인 경우) 부모를 재귀적으로 호출한다. 

 

이라고 보면된다.

 

동작방식을 그림으로 살펴보자

 

 

 

동작방식

 

이렇게 각 6개의 노드가 있다고 가정해보자.

 

그리고 노드의 번호와 부모를 자기 자신으로 초기화하면

노드번호	1	2	3	4	5	6
부모	1	2	3	4	5	6

이렇게 된다.

 

Union(1, 4) 연산을 해보자.

1의 루트노드는 1, 4의 루트노드는 4이다.

더 큰 루트노드인 4의 부모를 1로 세팅한다.

 

노드번호	1	2	3	4	5	6
부모	1	2	3	1	5	6

 

 

 

 

 

Union(2, 3) 연산

2의 루트노드 : 2

3의 루트노드 : 3

3의 부모를 2로 세팅.

노드번호	1	2	3	4	5	6
부모	1	2	2	1	5	6

 

 

 

 

 

 

Union(2, 4) 연산

2의 루트노드 : 2

4의 루트노드 : 1

2의 부모를 1로 세팅

 

노드번호	1	2	3	4	5	6
부모	1	1	2	1	5	6

 

 

 

Union(5, 6) 연산

5의 루트노드 : 5

6의 루트노드 : 6

6의 부모를 5로 세팅

노드번호	1	2	3	4	5	6
부모	1	1	2	1	5	5

 

 

 

 

 

코드로 구현

 

find_parent

해당 원소의 루트노드 찾기

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, x)
    return x

 

 

 

union_parent

각 원소의 루트노드중 큰 노드의 부모를 작은 노드으로 한다.

def union_parent(parent, a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

 

 

 

예시코드

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, x)
    return x


def union_parent(parent, a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


v, e = map(int, input().split())
parent = [0] * (v+1)

for i in range(1, v+1):
    parent[i] = i

for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

print("각 원소가 속한 집합: ", end=' ')
for i in range(1, v+1):
    print(find_parent(parent, i), end=' ')

print()

print("부모 테이블: ", end=' ')
for i in range(1, v+1):
    print(parent[i])

 

 

 

 

 

 

Union Find 자료구조를 이용한 사이클 판별

union find 자료구조의 find_parent 함수를 이용하면 사이클을 판별할 수 있다.

 

이 판별법은 무방향 그래프에서만 가능하고, 방향그래프일때는 DFS를 사용하면 된다

 

인덱스	1	2	3
부모	1	2	3

이렇게 무방향 그래프가 있다고 가정하고

Union(1, 2)

Union(1, 3)

Union(2, 3)

을 차례로 수행해보자.

 

 

 

Union(1, 2)

2의 루트는 2

1의 루트는 1

2의 부모를 1로 설정한다.

인덱스	1	2	3
부모	1	1	3

 

 

 

Union(1, 3)

1의 루트는 1

3의 루트는 3

3의 부모를 1로 설정한다.

인덱스	1	2	3
부모	1	1	1

 

 

 

 

Union (2, 3)

현재 위 그림에서 2와 3을 이으면 사이클이 생긴다

2와 3의 루트노드가 같기 때문이다.

 

그래서 Union을 하기 전에 항상 사이클인지 판별한다.

사이클인지 판별하기 위해서는 루트노드가 같은지 확인하면 된다.

 

2의 루트는 1

3의 루트는 1

사이클발생. Union을 실행하지 않는다.

 

 

 

 

 

사이클 판별을 추가한 코드

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, x)
    return x


def union_parent(parent, a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


v, e = map(int, input().split())
parent = [0] * (v+1)

for i in range(1, v+1):
    parent[i] = i

cycle = False

for i in range(e):
    a, b = map(int, input().split())
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)
        
if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")