서로소 집합 알고리즘

서로소 집합 알고리즘

 서로소 집합이란 공통 원소가 없는 두 집합을 말합니다. 따라서 어떤 그래프가 주어졌을 때 서로소 집합으로 분리하는 일련의 과정을 통해서 집합 간 관계를 파악할 수 있습니다. 이를 수행하는 알고리즘을 서로소 집합 알고리즘이라고 합니다.

 서로소 집합 알고리즘은 다음과 같은 순서로 처리됩니다.

---

1. Union 연산을 통해 서로 연결된 두 A,B를 체크한다.

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

3. 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야 한다.

---

 위와 같이 Union연산과 확인하는 Find연산으로 구성되어 있기 때문에, Union-Find 연산이라고도 합니다. 기본적으로는 다음과 같이 코드로 구현할 수 있습니다.

input1 = '''6 4
1 4
2 3
2 4
5 6'''

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return 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 = list(map(int, input1.split('\n')[0].split()))
array = [tuple(map(int, row.split())) for row in input1.split('\n')[1:]]
parent = [0] * (v + 1)

for i in range(1, v + 1):
    parent[i] = i
    
for i in range(e):
    a, b = array[i]
    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=' ')

 

 편의상 문자열로 입력을 받겠습니다. 이후 Union연산과 Find연산을 각각 정의해줍니다. Find 연산은 주어진 노드가 부모노드가 아니라면 상위노드를 재귀적으로 타고 올라가 부모 노드를 찾습니다. 부모 노드를 만나면 해당 노드를 그대로 반환합니다. 

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

 

 Union 연산은 위에서 정의한 Find 연산을 기반으로 연결된 두 노드에 대해서 부모 노드를 찾고, a의 부모노드가 b보다 작으면 b의 부모노드가 a가 되고, 반대의 경우 a의 부모노드가 b가 되는 방식입니다. 이는 인덱스가 낮은 노드가 더 상위의 노드라는 것을 가정합니다.

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

 

 각각의 노드에 대해서 부모를 자기 자신으로 초기화한 뒤, 연결된 노드 정보를 이용하여 부모 테이블을 업데이트 시켜줍니다.

parent = [0] * (v + 1)

for i in range(1, v + 1):
    parent[i] = i
    
for i in range(e):
    a, b = array[i]
    union_parent(parent, a, b)

 

---

경로 압축(Path Compression)

 다만 위와 같이 코드를 구성할 경우 부모를 찾을 때마다 재귀적으로 테이블 정보를 거슬러 올라가야한다는 단점이 있습니다. 따라서 이를 개선하기 위해 경로 압축(Path compression)을 고려해볼 필요가 있습니다. 전체 코드는 다음과 같습니다.

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 = list(map(int, input1.split('\n')[0].split()))
array = [tuple(map(int, row.split())) for row in input1.split('\n')[1:]]
parent = [0] * (v + 1)

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

for i in range(e):
    a,b = array[i]
    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=' ')

 

 앞선 코드와 유사하지만, 조금 다릅니다. 부모가 아닌 노드에 대해서 단순히 부모를 찾아 리턴했던 것과 달리, 루트노드를 찾을 때까지 테이블을 업데이트합니다. 또한 결과값으로 루트노드를 반환하는 것을 알 수 있습니다. 즉, 노드를 재귀적으로 탐색하는 것이 아니라 한 번에 루트노드, 즉 속한 집합을 조회할 수 있게 됩니다.

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

---

서로소 집합 알고리즘을 활용한 무향 그래프의 사이클 판별

 서로소 집합 알고리즘을 이용하면, 그래프의 사이클 여부를 판별할 수 있습니다. 예를 들어 다음과 같이 코드를 작성할 수 있을 것입니다.

input1 = '''3 3
1 2
1 3
2 3'''

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 = list(map(int, input1.split('\n')[0].split()))
array = [tuple(map(int, row.split())) for row in input1.split('\n')[1:]]
parent = [0] * (v + 1)

for i in range(v + 1):
    parent[i] = i
    
cycle = False # 사이클 발생 여부

for i in range(e):
    a, b = array[i]
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)
        
print('사이클 여부 :', '참' if cycle else '거짓')
print('부모 테이블 :', parent)

 일전과 유사하게 문자열로 입력을 받고, Union-Find 연산 정의했습니다. 테이블 업데이트가 종료된 뒤 연결된 노드 정보에 대해서 순회하며, 두 노드의 부모가 같은지 판별해줍니다. 만약 두 노드의 부모가 같다면 사이클이 발생한 것이라고 볼 수 있습니다. 무향 그래프에서 두 노드가 같은 집합에 속하고 연결되어 있다면 당연히 사이클이 발생한 것이기 때문입니다.

 이 때, 중요한 것은 꼭 경로 압축을 사용해야 한다는 점입니다. 두 노드가 같은 집합에 속하는지 부모 테이블로 판단하기 때문에, 재귀적으로 타고 올라가는 방식은 유효하지 않거나 혹은 비효율적입니다. 또한 무향 그래프에 대해서만 다음과 같이 사이클을 판별할 수 있습니다. 두 노드가 연결되어 있고 같은 집합에 속하지만, 방향이 달라 사이클이 발생하지 않을 수도 있기 때문입니다.