유니온 파인드

최근에 졸업 시험과 기업 코테를 포함하여 여러번 코테를 쳤다. 그중에서 n의 크기가 300,000으로, 아무리 봐도 최소 nlogn 안쪽으로 풀어야 할 것 같은데 완탐 풀이법밖에 생각나지 않는 문제들이 2개 있었다. 그들의 공통점은 union find로 풀어야 하는 문제였다는 것이었다. 첫번째 문제를 만났을 때 유니온 파인드를 공부했다면 다른 문제는 풀 수 있었을지도 모르는데... 역시 모르는게 생기면 공부를 바로바로 해야 한다.

유니온 파인드에 대하여

유니온 파인드의 다른 이름은 서로소 집합이다. 두 집합이 서로소 관계인지를 확인할 수 있다는 말은 각 집합이 어떤 원소를 공통으로 가지고 있는지 확인할 수 있다는 말과 같다. 그렇기 때문에 union-find라고 부른다.

기본 유형은 위 그래프의 연결 관계를 보고 아래와 같이 그룹으로 나누는 것이다.

맙소사! 졸업 시험 마지막 문제랑 똑같다.

졸업시험 마지막 문제 복기
a랑 b랑은 같은 그룹...c랑 a랑 같은 그룹... 이렇게 누구랑 누구랑 같은 그룹인지 알려주고 1~n 그룹에 속한 학생들을 종합적으로 정리해서 출력하는 문제.

이렇게 부모 노드를 기록할 수 있다면 노드들을 그룹지을 수 있을 것이다. 여기서 노드3의 경우 2를 가리키는데, 2는 1을 가리키고 있으므로 3은 노드1의 그룹에 속한다.

union이란?

사실 위 테이블을 만드는 건 딱 봐도 할 수 있을 것 같다. 걍 입력값으로 들어오는 애들을 테이블에 잘 정리해 넣으면 만들 수 있을 것이다. 이런 테이블로 만드는 걸 union 연산이라고 한다.

find란?

노드3같은 애들이 재귀적으로 가장 루트인 노드(이 경우엔 노드1)을 찾아가는 과정이 바로 find이다. 재귀 탈출 조건은 그 노드가 루트노드냐 아니냐가 될 것이다.

근데 그래프가 이렇게 생겼으면? '5번노드->4번노드->3번노드...0번노드' 이렇게 쭉 거슬러 가야 할 것이다. 최대 O(n)의 시간이 소요될 수 있다. 하지만 이 find 함수는 아주 간단한 과정으로 최적화가 가능하다. 그 방법은 바로 경로 압축 기법을 적용하는 것이다.

경로 압축이란?

경로 압축이란 find 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신하는 기법이다. find 함수를 호출하면 해당 노드의 루트 노드가 바로 부모 노드가 되도록 하는 것이다. 이렇게 하면 일일이 거슬러 가는것보다 더 빠르게 부모 노드에 거슬러 갈 수 있다.

# 특정한 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

경로 압축을 이용할 경우 시간 복잡도는, 노드가 v개이고 최대 v-1의 union 연산과 m개의 find연산이 가능할때 O(v+logv)이다. 300,000이라는 애매하기 짝이 없는 크기 제한이 여기서 나오지 않았을까 싶다.

유니온 파인드 예제 문제 풀이는 다음과 같다.

#이코테 298p
def find_parent(parent,x):
  if parent[x]!=x:
    #x의 부모의 부모를 찾기
    parent[x]=find_parent(parent,parent[x])
  return parent[x]
# a랑 b가 연결되어 있다는 정보가 주어지면, 테이블에 a,b 관계를 기록.
def union_parent(parent,a,b):
  a=find_parent(parent,a)
  b=find_parent(parent,b)
  #a,b가 연결되어 있으면 숫자가 더 작은 쪽이 부모
  if a<b:
    parent[b]=a
  else:
    parent[a]=b
n,m=list(map(int,input().split())) 
#부모 테이블 초기화
parent=[0]*(n+1)

#부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(0,n+1):
  parent[i]=i

#각 연산을 하나씩 확인
for i in range(m):
  oper,a,b=list(map(int,input().split()))
  #유니온 연산인 경우
  if oper==0:
    union_parent(parent,a,b)
  else:
    if find_parent(parent,a)==find_parent(parent,b):
      print("YES")
    else:
      print("NO")

유니온 파인드를 이용한 사이클 판별

서로소 집합은 무방향 그래프 내에서 사이클을 판별할 때 사용할 수 있다. (참고로 방향 그래프에서의 사이클 여부는 dfs를 이용하여 풀 수 있다.) 부모 테이블을 봤을때 부모노드가 같은 노드를 가리키면 사이클이 있다고 판단 가능하다.

참고: 이코테 268p

이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다.