📌유니온 파인드(Union-Find)를 알아보자 (이코테 WITH 파이썬)

어젯밤 알고리즘 스터디 모의 코테 중 못 푼 문제가 있는데 검색해보니 유니온 파인드로 푼다고 했다. 유니온 파인드가 뭔지 알아보고 못 풀었던 백준 문제도 풀어보겠다😇

 

유니온 파인드

우선 서로소 집합(Disjoint Sets)에 대해 알아야 한다. 서로소 집합은 공통 원소가 없는 두 집합을 말한다. 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 데이터를 처리하기 위한 자료구조이며, union과 find 연산으로 조작할 수 있기 때문에 유니온 파인드 자료구조라 불리기도 한다.

 

• union: 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• find: 특정 원소가 어느 집합에 포함되어있는지 찾는 연산

 

유니온 파인드 알고리즘은 서로소 집합을 표현하기 위한 알고리즘이다. 이를 통해 각 집합이 어떤 원소를 공통적으로 갖고 있는지 확인할 수 있다.

 

코드 구현

유니온 파인드는 트리 자료구조로 구현하며, 각 원소의 부모를 나타내는 부모 테이블을 정의해 연산을 진행한다.

 

# 루트 노드 찾기
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 = map(int, input().split())
parent = [0] * (v + 1)

# 부모 테이블 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# union 연산
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

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

print()

print('부모 테이블')
for i in range(1, v + 1):
    print(parent[i], end=' ')
    
'''
입력
6 4
1 4
2 3
2 4
5 6

출력
각 원소가 속한 집합
1 1 1 1 5 5 
부모 테이블
1 1 2 1 5 5 
'''

 

이때 출력을 보면 노드 3의 부모 노드가 2인 것을 볼 수 있다. 이는 노드 3의 루트를 찾기 위해서는 부모 노드인 2로 이동한 후, 다시 2의 부모 노드인 1로 이동해야 한다는 것을 의미한다. 

 

부모 노드를 거슬러 올라가는 방식은 노드의 개수가 V일 때 최대 O(V)의 시간이 소요된다. 연산의 개수가 M개 일 때 전체 시간 복잡도는 O(VM)이되어 비효율적이라 할 수 있다.

 

경로 압축  

시간복잡도를 줄이기 위해 find 연산에서 경로 압축 기법을 사용할 수 있다.

 

def find_parent(parent, x):
    # 루트 노드를 찾을 때 까지 재귀적으로 호출
    if parent[x] != x:
        # return find_parent(parent, parent[x]
        parent[x] = find_parent(parent, parent[x])
    # return x
    return parent[x]
 
'''
부모 테이블
1 1 1 1 5 5 
'''

 

위와 같이 찾은 루트 노드가 바로 부모 노드가 되게 하면 트리의 높이가 압축되어 효율적으로 find 연산을 할 수 있다. 

 

문제 풀이

그럼 백준의 여러분의 다리가 되어 드리겠습니다! 문제를 다시 풀어보자.

 

BOJ

BOJ

 

아무거나 한 방법만 출력하면 되는 제목도 내용도 신기한 문제였다. 서로 왕복할 수 없는 섬을 찾는 것은 서로소 집합을 찾는 것이나 마찬가지이기 때문에 유니온 파인드를 사용하면 되겠다.

 

import sys
input = sys.stdin.readline

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 = int(input())
parent = [0] * (v + 1)

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

for _ in range(v - 2):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

root = find_parent(parent, 1)
for i in range(2, v + 1):
    if find_parent(parent, i) != root:
        print(root, i)
        break

 

앞선 코드를 그대로 적용하되 마지막 부분만 바꿔주었다. 

 

1) 입력으로 주어진 연산을 한다.

2) 첫번째 노드의 루트 노드를 찾아 root 변수에 넣는다. 

3) 두 번째 노드부터 루트 노드를 찾아 root 값과 다른 경우 출력한다. 

 

*시간초과가 나는 경우 sys 라이브러리를 사용하자.

 

---

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고

 

17352번: 여러분의 다리가 되어 드리겠습니다!