Union-Find 알고리즘

union-find(합집합 찾기) 알고리즘은 disjoint set(서로소 집합)으로 불리기도 한다.

개념

• union-find는 서로 중복되지 않은 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.
• 여러 개의 노드가 존재할 때 두개의 노드를 선택해서 이 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.
• Kruskal 알고리즘에 활용되기 때문에 정확하게 이해해야하는 개념이다.

Union

2개의 원소로 이루어진 집합을 하나의 집합으로 합치는 연산

Find

두개의 원소가 같은 그래프에 속하는지 판별하는 연산

구현

1. 초기화

각 노드의 부모노드를 노드 번호로 초기화

parent = []
for i in range(n+1):
	parent.append(i)

2. 부모노드 찾기

재귀적으로 부모노드를 찾는다. => 부모노드와 현재 자기 지신의 노드를 반환하면 그 노드가 부모노드라는 뜻이므로 그대로 반환하고, 그렇지 않으면 재귀적으로 해당 요소의 값을 이용해 부모노드의 값을 찾는다.

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

3. union 연산

부모를 합칠때는 일반적으로 더 작은 값쪽으로 합친다.

def union_parent(parent,a,b):
	a = get_find(parent,a)
    	b = get_find(parent,b)
        if a < b :
        	parent[b] = a
       	else :
        	parent[a] = b

4. find 연산

두개의 노드가 같은 그래프에 속하는지 판별

def find_parent(parent,a,b):
	a = get_find(parent,a)
    	b = get_find(parent,b)
        if a == b:
        	return 1
        else:
        	return 0

개선된 find 연산

위의 그림에서 보면 5번째 노드의 부모도느를 찾기 위해서 5 -> 4 -> 1의 과정을 거치게된다. 만약 굉장히 긴 트리구조에서 leaf 노드의 부모노드를 찾는다면 굉장히 비효율적일 것이다.

위와 같이 바꾼다면 더 빠르게 루트노드를 파악할 수 있다.

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

사이클 판별법

union find 알고리즘을 활용해서 그래프 내의 사이클을 판별할 수 있다.

1. 두 노드의 루트 노드를 확인한다.
   1-1 루트노드가 다르면 => Union 연산
   1-2 루트노드가 같으면 => cycle 발생
2. 모든 간선에 대해 1을 반복

for i in range(e):
  a, b = map(int, input().split())
  if find_parent(parent, a, b):
      cycle = True
      break
  else:
      union_parent(parent, a, b)

reference

참고 블로그1
참고 블로그2
참고 블로그3