[알고리즘] Union-Find(합집합 찾기)

Union-Find 자료구조란?

각각의 독립된 데이터들을 그룹화 시켜 관리할 때 사용하는 자료구조이다. 두 그룹울 그룹화 시킬 때 각 그룹의 보스 데이터를 하나로 합친다. 그래서 임의의 두 데이터가 같은 그룹인지 아닌지를 확인할 때 각 데이터가 속한 그룹의 보스가 같은지 여부를 판단한다.

🎈Union-Find의 시간 복잡도

Union-Find의 시간 복잡도는 구하기가 꽤 까다롭다. 최적화 여부, 순서 등에 따라 매번 달라지기 때문이다. 코드를 살펴보면 전체 시간 복잡도와 Union 함수의 시간 복잡도는 Find 함수의 시간 복잡도에 따라 결정되는 것을 알 수 있다.

경로 압축 최적화를 하지 않은 경우, 트리가 한 쪽으로 치우칠 수 있기 때문에 Find 함수의 시간 복잡도는 최악의 경우O(N)이다.

경로 압축 최적화를 한 경우, 트리가 짧고 넓은 형태가 될 가능성이 높아지므로O(logN) 정도로 생각하면 된다.

실제 시간 복잡도는O(α(N))라고 한다. α(x)는 애커만 함수라고 하는데, x가 2의 65536제곱일 때 함수 값이 5가 된다. 따라서, 그냥 상수라고 봐도 무방하다.

구현 코드

arr=[0]*200 # 어떤 데이터의 보스를 저장할 배열, 데이터의 아스키 코드가 index가 된다. 

def findboss(member):
    global arr
    if arr[ord(member)]==0: # 매개변수에 해당하는 곳의 값이 0이라면
        return member       # 자기 자신이 보스!!
    ret=findboss(arr[ord(member)]) # 배열에 적혀있는 값으로 다시 보스 찾아보기
    return ret

def union(a,b):
    global arr
    aboss=findboss(a)  # boss 찾기
    bboss=findboss(b)
    if aboss == bboss:  # boss가 같다 -> 이미 같은 그룹
        return
    arr[ord(bboss)] = aboss  # 두보스가 다르다면 b의 보스를 a그룹의 보스로 만든다.

union('A','B') # 두 그룹을 하나의 그룹으로 합치는 함수
union('D','E') 
union('B','E')
union('B','D')
union('F','E')

y,x=input().split()

if findboss(y)==findboss(x): # 같은 그룹 여부를 print
    print("같은그룹")
else: print("다른그룹")

# union find 자료구조를 이용하여 양방향 그래프에서의 cycle 존재여부 확인

n=int(input())
edge=[]
for _ in range(n):
    edge.append(input().split()) 

arr=[0]*200

def findboss(member):
    global arr
    if arr[ord(member)] == 0:
        return member
    ret=findboss(arr[ord(member)])
    arr[ord(member)] = ret             # 경로 압축(Path Compression)
    return ret

# union 함수
def union(a,b):
    global arr

    fa,fb=findboss(a),findboss(b)
    if fa==fb: return 1                # 같은 그룹이면 return 1 (사이클 완성)
    arr[ord(fb)]=fa

answer=0
for i in range(n):
    a,b=edge[i]
    ret=union(a,b)
    if ret==1:
        answer=1
        break
if answer: print("cycle 발견")
else: print("cycle 미발견")

# 입력
# A B
# C D
# B C
# A E

# 출력
# cycle 발견

💡Union-Find 활용 문제

• 민코딩
  • Minco 스테이크 하우스
  • 춘추 전국 시대
• SWEA
  • 그룹 나누기