Union-Find 알고리즘

오늘 소개할 알고리즘은 union-find 알고리즘이다. 해당 알고리즘에 대해 알게 된 건 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 = map(int, input().split())
parent = [0] * (v + 1)

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

for i in range(e):
    a, b = map(int, input().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 = ' ')

# 입력 예시
# 6 4
# 1 4
# 2 3
# 2 4
# 5 6

함수를 먼저 설명하자면 이렇다. find_parent 함수는 해당 원소의 부모를 찾아주는 함수이다. 쉽게 말해 속해 있는 집합의 대표자를 찾는 함수이다. parent 리스트와 원소 x를 파라미터로 받는다. 이때 만약 원소 x가 parent[x]의 값과 다르다면, 리스트의 값이 어떤 부모를 갖는지 다시 확인해야 한다. 이를 위해 재귀함수를 이용한다. 만약 일치한다면 parent[x]를 그대로 반환한다. 이는 재귀함수가 완료되어 빠져나갈 때 parent 리스트에 모두 동일한 값이 저장될 수 있도록 한다. 즉, 해당 함수가 실행되고 나면 원소 x가 속한 집합의 대표자를 알 수 있게 된다. 

다음으로 union_parent 함수를 살펴보자. 함수의 역할은 서로 다른 원소가 한 집합에 속할 수 있도록 합쳐주는 것이다. 이 함수는 파라미터로 parent 리스트와 원소 a, b를 받는다. 우선 원소 a와 원소 b의 부모를 find_parent 함수를 이용해 찾은 뒤, 더 낮은 값을 갖는 부모가 다른 원소의 부모가 될 수 있도록 한다. 더 낮은 값을 갖는 것으로 정한 이유는 하나의 기준을 마련하기 위한 장치로 이는 개개인의 성향에 따라 다르게 설정할 수 있다.

 

중요한 함수 두 가지를 살펴보았다. 이제 전반적인 코드가 어떻게 수행되는지 살펴보자.

입력으로는 전체 원소의 수와 다음으로 입력받을 연결 관계의 수를 우선 받는다. 이를 활용해 parent 리스트를 각각 원소의 부모가 자기 자신이 되도록 초기화 해둔다. 이후 연결 관계를 입력받는다. 이때 union_parent 함수를 이용해 즉시 속하는 집단이 어디인지 체크하게 한다. 이렇게 하면 전체적인 연결관계가 정리된다.

 

print 하는 부분은 코드가 제대로 작동하는지 확인하기 위한 부분으로, parent 리스트의 출력을 통해 확인할 수 있다.

---

개념 자체는 어렵지 않으나 생소하고 처음 접한다면 바로 코드를 짜기 어렵다 생각한다. 앞으로 하나씩 정리해가며 스스로 능력을 키울 수 있도록 하자. 오늘 글은 여기서 마무리하겠다.