🚀 Union_Find(서로소 집합 자료구조)
Union_Find 자료구조는 스택의 pop, push처럼 Union(합집합), Find(찾기) 연산으로 구성된다.
- Union 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다.
- A와 B의 루트 노드 A`, B`를 각각 찾는다.
- A`를 B`의 부모 노드로 설정한다.(B`가 A`를 가리키도록 한다.) - 모든 Union 연산을 처리할 때까지 1번 과정을 반복한다.
실제로 구현 할 때는 A`와 B`중에서 더 번호가 작은 원소가 부모노드가 되도록 구현하는 경우가 많다.
초기 단계에서 각자 자기 자신을 부모로 가지도록 초기화 한다.
Union 1,4
- 현재 각각 루트 노드가 1과 4이기 때문에 둘 중 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.
Union 2,3
- 위와 똑같이 3 노드의 부모를 2로 설정한다.
Union 5,6
- 마지막으로 5와 6을 합치면 끝이 난다.
🔥 기본적인 Union_find 알고리즘의 python코드는 다음과 같다.
from sys import stdin as s
s = open('input.txt','rt')
# 특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
#루트 노드가 아니라면 ,루트 노드를 찾을 때까지 재귀적으로 호출
# if parent[x] != x:
# return find_parent(parent,parent[x])
# return x
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent,a,b):
a = find_parent(parent,a)
b = find_parent(parent,b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선(union 연산)의 개수 입력 받기
v, e = list(map(int,s.readline().split()))
parent = [0] * (v + 1) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
# union 연산을 각각 수행
for i in range(e):
a, b = list(map(int, s.readline().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], end= ' ')
해당 알고리즘은 무방향 그래프 내에서 사이클을 판별할 때 사용할 수 있다.
- 방향 그래프에서의 사이클 여부는 DFS로 판별할 수 있다.
# 위의 코드에서 해당 부분만 변경하면 사이클을 판단할 수 있다.
cycle = False # 사이클 발생 여부
# union 연산을 각각 수행
for i in range(e):
a, b = list(map(int, s.readline().split()))
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent,b):
cycle = True
break
# 사이클이 발생하지 않았다면 합집합 수행
else:
union_parent(parent,a,b)
if cycle:
print("사이클 발생")
else:
print("사이클 발생하지 않음")🚀 Union_Find(서로소 집합 자료구조)
Union_Find 자료구조는 스택의 pop, push처럼 Union(합집합), Find(찾기) 연산으로 구성된다.
- Union 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다.
- A와 B의 루트 노드 A`, B`를 각각 찾는다.
- A`를 B`의 부모 노드로 설정한다.(B`가 A`를 가리키도록 한다.) - 모든 Union 연산을 처리할 때까지 1번 과정을 반복한다.
실제로 구현 할 때는 A`와 B`중에서 더 번호가 작은 원소가 부모노드가 되도록 구현하는 경우가 많다.
초기 단계에서 각자 자기 자신을 부모로 가지도록 초기화 한다.
Union 1,4
- 현재 각각 루트 노드가 1과 4이기 때문에 둘 중 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.
Union 2,3
- 위와 똑같이 3 노드의 부모를 2로 설정한다.
Union 5,6
- 마지막으로 5와 6을 합치면 끝이 난다.
🔥 기본적인 Union_find 알고리즘의 python코드는 다음과 같다.
from sys import stdin as s
s = open('input.txt','rt')
# 특정 원소가 속한 집합을 찾기
def find_parent(parent,x):
#루트 노드가 아니라면 ,루트 노드를 찾을 때까지 재귀적으로 호출
# if parent[x] != x:
# return find_parent(parent,parent[x])
# return x
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent,a,b):
a = find_parent(parent,a)
b = find_parent(parent,b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선(union 연산)의 개수 입력 받기
v, e = list(map(int,s.readline().split()))
parent = [0] * (v + 1) # 부모 테이블 초기화
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
# union 연산을 각각 수행
for i in range(e):
a, b = list(map(int, s.readline().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], end= ' ')
해당 알고리즘은 무방향 그래프 내에서 사이클을 판별할 때 사용할 수 있다.
- 방향 그래프에서의 사이클 여부는 DFS로 판별할 수 있다.
# 위의 코드에서 해당 부분만 변경하면 사이클을 판단할 수 있다.
cycle = False # 사이클 발생 여부
# union 연산을 각각 수행
for i in range(e):
a, b = list(map(int, s.readline().split()))
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent,b):
cycle = True
break
# 사이클이 발생하지 않았다면 합집합 수행
else:
union_parent(parent,a,b)
if cycle:
print("사이클 발생")
else:
print("사이클 발생하지 않음")