Union , Find

백준에서 나온 문제 중에서 최소 신장트리를 이용한 문제가 있었다. 해당 알고리즘이 필요하기 위해서 선제적으로 알아야할 개념인 서로소 집합 자료구조에 대해서 알아보고자 한다.

그리디 알고리즘이라고 할 수 있는 Kruscal Algorithm과 Stack, Queue를 활용해야하는 위상정렬 알고리즘이 그래프 알고리즘의 종류이다

 

우선 Edge와 Node로 이루어져 있는 그래프 데이터들은 다익스트라 알고리즘과 같은 '최단 경로 알고리즘'과 stack과 재귀함수를 사용하여 DFS,BFS 활용할 때 주로 이루었다.

따라서 '서로 다른 객체가 연결되어 있다'는 이야기를 들었다면 반사적으로 그래프 데이터를 활용한 알고리즘이 떠오른다.

• 메모리 측면에서 인접형렬이 저장한 정보는 많다. 따라서 노드간에 연결되지 않은 정보도 0이라는 것을 저장하기 때문에 O(V²) 시간 복잡도가 걸린다. 하지만 인접리스트의 경우 제일 안좋은 상황이면 전체 노드의 개수인 O(V) 만큼 시간 복잡도가 걸린다.

==> 따라서 그래프 데이터를 활용하는 문제를 본다면, 메모리&속도 면에서 효율성이 높은 그래프 알고리즘을 선택하면 된다.

 

 

서로소 집합 자료구조

교집합이 없는 서로 다른 집합을 일컫는다. {1,2} , {5,6} 과 같이 서로소 집합은 원소들의 공통요소가 없는것을 말한다.

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

 

여기서 서로소 집합 자료구조는 합집합 연산 기호인 union과 찾기 연산 기호인 find 연산으로 이루어져 있다.

 

Union / Find

1. union 연산 확인 : 서로 연결된 두 노드를 확인한다

  1.1 A의 루트 노드 A'과 B의 루트 노드 B'를 찾는다 (Find)

  1.2 A'를 B'의 부모 노드로 설정한다 (A' < B')

2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.

 

만약 1~6까지의 집합과 4개의 union 연산 (1,4) (2,3) (2,4) (5,6)이 주어졌다한다면 다음과 같이 구성된다

첫번째로 부모 테이블의 초기화를 한다.

- 노드의 개수 크기이 부모 테이블을 초기화를 시킨다.

0을 인자로 가져도 상관 없지만 어떤 방법이든 초기화를 시켜준다. 여기선 자기 자신을 부모로 가지도록 설정한다

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

 

두번째로 union 연산을 한다.

ex: union (1,4) --> 1과 4의 루트 노드를 찾아 더 큰 번호인 루트 노드 4의 부모를 1로 결정한다

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

 

두번째에서 본 과정인 union을 (1,4) (2,3) (1,2) (5,6)을 수행한다

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

 

• 문제점 : 비효율성

만약 정점은 1~5까지 있고, union 연산이 (4,5)(3,4) (2,3) (1,2)라고 할 때, 부모테이블은 다음과 같다

노드	1	2	3	4	5
부모	1	1	2	3	4

해당 경우에서는 5의 루트를 찾기위해서 O(V) 의 시간이 소요된다.

따라서 노드의 개수 V, union이나 find 연산 개수 M개라고 할 때 최악의 경우 O(VM) 시간이 소요된다

 

 

Find 함수 개선

경로 압축을 이용해서 최적화를 실시한다. find 함수를 return 값을 수정하여 부모테이블 또한 루트노드에 빠르게 접근하도록 한다.

import sys
input = sys.stdin.readline
V,E = map(int,input().split()) #정점의 개수 : V , 간선의 개수 : E
result = 0 # 최종 신장 갯수

#부모 테이블 초기화
parent = [0] * (V+1)
for i in range(1, V+1):
    parent[i] = i

# find 연산
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# union 연산
def union(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

edges = [] # 간선 정보

# 간선 정보 주고 비용 정렬
for _ in range(E):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))
    
# 간선 정보를 오름차순 정렬
edges.sort()

#간선정보 확인하여 kruscal 수행
for i in range(E):
    cost, a, b = edges[i]
    # find 연산 후, 부모노드가 다르면 사이클 발생 X -> union 연산
    if find_parent(parent,a) != find_parent(parent,b):
        union(parent,a,b)
        result += cost

print(result)

 

사이클 판별

서로소 집합은 간선에 방향이 없는 무방향 그래프 내에서 사이클을 판별 할 때 사용이 가능하다.

Union 연산 정보가 주어질 때, 즉 간선 정보가 주어질 때, 간선 하나하나 확인하면서 Find 연산을 취하여 각 노드의 부모노드를 찾는다.

그리고 찾아낸 2개의 부모 노드들이 같다면 사이클이 있다고 판단한다. 만약 그렇지 않으면 Union 연산으로 부모-자식 노드 관계를 만든다.