[그래프] 서로소 집합(Disjoint sets)

● 서로소[Disjoint] 집합 : 서로 중복 포함된 원소가 없는 집합 (교집합 x)

1. 서로소 집합의 특징

1. 서로소 집합을 표현하는 방법으론 연결 리스트와 트리 방식이 있다.

2. 서로소 집합의 자료구조는 Union-find 자료구조라고 불린다.

3. 두 집합의 서로소를 파악할수 있다면, 각 집합이 어떤 원소를 공통으로 가지고 있는지 알수 있다.

 

2. 서로소 집합 과정

1. make-set(x) : 모든 원소를 초기화시켜주어 새로운 집합을 생성하는 과정

for i in range(1, v+1):
	parent[i] = i
# 맨 처음은 자기자신의 인덱스의 값을 부모로 가지도록 설정하여, 최종적인 루트노드를 찾아가면 바꿔준다.

---

2. find-set(x) : 특정 원소가 속한 집단이 어떤 집단이 찾는 과정

1.1. 재귀함수 사용

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

1.2. 반복문 사용

def find(parent, x):
    while parent[x] != x:
        x = parent[x]
    return x

1.3. 경로압축

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

---

3. Union(x) : 2개의 원소가 포함된 집합을 하나로 합치는 과정 

def Union (parent, x, y):
	a = find(parent, x)
    b = find(parent, y)
    if a < b:
    	parent[b] = a
    else :
    	parent[a] = b

---

3. 서로소 집합 구현

3.1. 기본정렬

# 특정 원소가 속한 부모노드 끝까지 확인
def find_parent (parent, 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

v, e = map(int, input().split()) # 노드의 개수와 간선의 개수 입력
parent = [0] * (v+1) # 부모 노드 초기화

# 부모노드에 자기자신을 대입
for i in range(1, v+1):
	parent[i] = i

# union 연산 진행
for i in range(1, v+1):
  a, b = map(int, input().split()) # 각 union 연산 입력
  union_parent(parent, a, b)

# 각 집합의 부모노드 확인
for i in range(1, v+1) :
  print (find_parent(parent, i), end=" ")

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

 

3.2. 서로소를 이용한 사이클 판별

# 특정 원소가 속한 부모노드 끝까지 확인
def find_parent (parent, 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

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(1, v+1):
  a, b = map(int, input().split()) # 각 union 연산 입력
  if find_parent(parent, a) == find_parent(parent, b):
  	cycle = True
    break
  else :
  	union_parent(parent, a,b)
  
  # 사이클 발생 여부
  if cycle:
  	print("사이클 발생")
  else :
  	print("사이클 미발생")

---

참고서적

 

이것이 취업을 위한 코딩 테스트다 with 파이썬 (취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드)