집합 - 몸풀기 문제

### 문제 33 간단한 유니온-파인드 알고리즘 구현하기

상호배타적 집합을 표현하고 관리하는데 다음 두 연산이 필요

• union(x,y) : x와 y가 속한 두 집합을 합침
• find(x) : x가 속한 집합의 대표 원소를 찾음

초기의 노드는 부모 노드를 자신의 값으로 설정했다고 가정
루트 노드가 작은 노드를 더 큰 노드의 자식으로 연결하는 방법 사용
operations 모두 수행한 후 집합의 개수 반환

operations는 ['u',1,2], ['f',1] 이런식으로 나옴

def find(parents,x):
	if parents[x]=x:
    	return x
    parents[x]=find(parents,parents[x])
    return parents[x]

def union(parents,x,y):
	root1=find(parents,x)
    root2=find(parents,y)
    parents[root2]=root1
    
def solution(k,operations):
	parent=list(range(k))
    n=k
    for op in operations:
    	if op[0]=="u":
        	union(parents,op[1],op[2])
        elif op[1]=="f":
        	find(parents,op[1])
    n=len(set(find(parents,i) for i in range(k))) # set 으로 중복 제거
    return n

** 재귀함수
자기 자신을 호출하는 함수
즉, 함수 내부에서 다시 자기 자신을 호출하여 특정 작업을 반복적으로 수행

재귀 함수의 구조

• 종료 조건(Base Case):
  재귀 호출을 멈추기 위한 조건
• 재귀 호출(Recursive Case):
  함수가 자기 자신을 호출하여 더 작은 문제를 해결