[백준] 1717번 집합의 표현 (유니온 파인드 문제)

사용 언어 - Python3, PyPy3

문제 -  1717번 집합의 표현

유니온 파인드 union & find

두 노드, 두 숫자, 두 무언가가 같은 집합 안에 있나요?

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

정답

유니온 파인드

x==0 인 경우, 두 집합 합치기 _union(a,b)

- 부모 리스트 생성

par = [i for i in range(n+1)] 부모는 자기자신으로 시작

- 관계 생성 a = b의 부모

par[b] = a

x==1인 경우, 두 집합이 같은 집합인지 확인하기 _find(a) == _find(b)

부모 찾기 _find(a)

- 부모가 없는 경우 = 부모가 자기자신인 경우

par[a] == a:

 

- 부모 있는 경우

부모의 부모의 부모.. 가장 윗 노드의 부모(루트노드) 찾기 _find(par[a])

 

=> 노드가 많아질수록, 계산량 많아짐. 시간 복잡도 증가 => 유니온 파인드의 최적화 필요!!!!!

1. FIND 최적화

- 경로단축

부모가 있는 경우, a의 부모 = a의 부모의 부모의 부모,,, 가장 윗 노드의 부모로 업데이트하기

par[a] = _find(par[a])

 

2. UNION 최적화 => FIND는 재귀함수라, UNION 최적화가 파이썬에서 더 유력

2.1. 머리끼리 붙인다.

a랑 b를 붙이지 말고, a의 머리와 b의 머리를 찾아서 머리끼리 붙이면 불필요한 계산 줄일 수 있다.

a = _find(a)

b = _find(b)

 

2.2 depth가 큰 집합에 작은 집합을 붙인다.

a와 b를 합칠 때, 더 depth가 큰 집합에 붙이는게 시간 복잡도가 줄어든다.

 

- depth를 저장할 rank 리스트 생성

rank = [0 for _ in range(n+1)]

 

- a와 b 값이 같다면, 합칠 필요 없음 return a

 

- rank[a] < rank[b] 라면,

par[a] = b, a의 부모 = b, a를 b 밑에 붙인다

 

- rank[b] < rank[a] 라면,

par[b] = a, a = b의 부모

 

- rank[a] == rank[b] 라면,

두 depth가 같으므로 아무거나 붙여도 상관없다.

par[a] = b 로 할거면, rank[b] += 1

par[b] = a 로 할거면, rank[a] += 1

 

UNION 최적화 활용 답안

def _union(a,b):
    # 유니온 최적화
    # 1. 머리끼리 합치기. 쓸데없는 find를 안하도록
    a = _find(a)
    b = _find(b)
    # 2. depth가 큰 집합에 작은 집합 붙이기. 
    if a == b:
        return
    if rank[a] < rank[b]:
        par[a] = b # a의 부모 = b로 붙이기
    elif rank[b] < rank[a]:
        par[b] = a
    else:
        par[a] = b # 반대로 해도 상관없음
        rank[b] += 1 # b의 depth가 1개 증가

def _find(a):
    if par[a] != a:
        par[a] =  _find(par[a])
    return par[a]

n,m = map(int,input().split()) # 집합개수, 연산개수
rank = [0 for _ in range(n+1)] # 점프할 수 있는 칸 = 0칸에서 시작 = depth
par = [i for i in range(n+1)] # 스스로가 부모인 상태에서 시작

for _ in range(m):
    x,a,b = map(int,input().split())
    if x == 0: # 두 집합 합하기 union
        _union(a,b)
    if x == 1: # 두 집합이 같은 집합인가? find
        if _find(a) == _find(b):
            print("YES") 
        else:
            print("NO")

 

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1717_%EC%A7%91%ED%95%A9%EC%9D%98%ED%91%9C%ED%98%84.py