[알고리즘] 서로소 집합 - Disjoint Sets

 

 

서로소 집합

---

서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 예를 들어 {1, 2}와 {3, 4}의 집합이 있다면 두 집합은 서로 서로소 관계이다. 만약 여기에 {2, 3} 의 관계를 나타낸다면 모두 서로소 관계가 아닌 것을 확인할 수 있다. 서로소 개념은 그래프 알고리즘에서 중요하게 사용되는 경우가 있어서 잘 알아두어야 한다.

그래서 서로소 집합 자료구조 (union-find 자료구조)는 서로소 부분 집합들로 나누어진 원소들을 처리하기 위한 자료구조라고 할 수 있다. 이는 union과 find 두 개의 연산자를 사용한다. union은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산을 담당하고 find 연산은 특정한 원소가 속한 집합을 찾는 연산을 담당한다.

 

 

서로소 집합 알고리즘

---

기본적으로 서로소 집합 자료구조는 트리 구조를 기반으로 구현한다. 

서로소 집합 정보가 주어졌을때 어떻게 집합을 표현하는지 알아보려고 한다.

 

 - union 연산을 확인하면서 서로 연결된 두 노드의 A, B를 확인

 - A, B의 루트노드 A', B'를 각각 찾음 (일반적으로 원소번호가 더 작은 쪽이 부모 노드가 되도록 구현하는 것이 일반적)

 - A'를 B'의 부모 노드로 설정

 - B'가 A'를 가리키도록 함

 - 모든 union 연산을 처리할때까지 위 과정을 반복

 

 - union 1, 4 (1과 4는 같은 집합)

 - union 2, 3 (2와 3은 같은 집합)

 - union 2, 4 (2와 4는 같은 집합)

 - union 5, 6 (5와 6은 같은 집합)

 

첫번째, 노드 개수 V 크기의 부모 테이블을 초기화 / 모든 원소가 자기 자신을 부모로 가진다고 가정하여 6개의 트리가 있다고 생각하면 됨 /  V = 6 

노드 번호 : 1, 2, 3, 4, 5, 6

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

 

두번째, union 1, 4 연산을 수행 / 1과 4가 합쳐지며 이때 더 작은 숫자가 더 작은 1번이 4번의 부모 노드가 됨 / 부모 테이블 갱신

노드 번호 : 1, 2, 3, 4, 5, 6

부모 노드 : 1, 2, 3, 1, 5, 6

 

세번째, union 2, 3 연산 수행 / 2와 3이 합쳐지며 이때 더 작은 숫자가 더 작은 2번이 3번의 부모 노그다 윔 / 부모 테이블 갱신

노드 번호 : 1, 2, 3, 4, 5, 6

부모 노드 : 1, 2, 2, 1, 5, 6

 

네번째, union 2, 4 연산 수행 / 2와 4가 합쳐지며 이때 각각의 부모는 2, 1이기 때문에 2의 부모를 1로 변경

노드 번호 : 1, 2, 3, 4, 5, 6

부모 노드 : 1, 1, 2, 1, 5, 6

 

다섯째, union 5, 6 연산 수행 / 5가 6보다 작으므로 5가 6의 부모로 변경

노드 번호 : 1, 2, 3, 4, 5, 6

부모 노드 : 1, 1, 2, 1, 5, 5

 

 

서로소 집합 알고리즘 코드 구현

---

루트노드를 찾아주는 함수를 구현한다.

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

노드와 union 연산의 개수를 입력받는다. 그리고 부모 테이블을 모두 자기자신으로 초기화시킨 다음 union 연산을 수행한다.

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

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

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

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

print('부모 테이블: {}'.format(parent))

실행 결과는 다음과 같다. 6개의 노드가 존재하고 4개의 union연산을 수행한 결과이다.

 

 

서로소 집합 알고리즘 사이클 확인

---

서로소 집합 알고리즘은 무방향 그래프 내에서의 사이클을 판별할때 사용할 수 있다. (방향 그래프의 사이클은 DFS로 판별할 수 있다고 한다) 그래프의 사이클은 특정 노드에서 시작했을때 자기 자신으로 돌아오는 경로가 있다면 사이클이 존재한다고 할 수 있다. union연산은 그래프에서의 간선을 표현하기 때문에 간선을 확인해서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하여 사이클을 판단할 수 있다.

 - 간선을 확인하여 두 노드의 루트노드를 확인

 - 루트노드가 서로 다르다면 두 노드에 대해 union 연산 수행

 - 루트노드가 서로 같다면 사이클이 존재하는 것

 

예시로 1 - 2 - 3 - 1 이렇게 3개의 노드가 사이클로 연결되어있다라고 가정해보도록 한다.

첫번째, 모든 노드에 대해 부모 테이블을 초기화 한다.

노드 번호 : 1, 2, 3

부모 노드 : 1, 2, 3

 

두번째, 1 - 2 간선을 확인 / 두 노드의 루트노드가 다르므로 union 연산 수행 / 1이 2 보다 작으므로 1이 2의 루트노드가 됨

노드 번호 : 1, 2, 3

부모 노드 : 1, 1, 3

 

세번째, 1 - 3 간선 확인 / 두 노드의 루트노드가 다르므로 union연산 수행 / 1이 3보다 작으므로 1이 3의 루트노드가 됨

노드 번호 : 1, 2, 3

부모 노드 : 1, 1, 1

 

네번째, 2 - 3 간선 확인 / 루트노드가 같으면 싸이클이 존재한다고 판단

 

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

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

cycle = False

for _ 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("사이클이 발생하지 않았습니다.")

 

 

Reference

---

https://katfun.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0

그래프 이론

https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

서로소 집합 자료 구조 - 위키백과, 우리 모두의 백과사전

https://coding-factory.tistory.com/610

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

https://katfun.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0

그래프 이론