유니온 파인드란?
유니온 파인드: 두 노드가 같은 집합에 속하는지 판별하는 알고리즘
→ 유니온 : 두 노드를 합치는 연산
→ 파인드: 두 노드의 루트 노드를 찾는 연산
파인드 연산에서 고려해볼 것
a) 각 배열에 자신의 부모 노드를 저장해놓고 이를 파인드 연산에 활용한다
- 리프 노드가 차례로 다른 노드를 거쳐서 타고 올라가 루트 노드를 만나게 된다
b) 각 배열에 자신의 루트 노드를 저장해놓고 이를 파인드 연산에 활용한다
- 리프 노드와 루트노드가 바로 연결되기 때문에, 루트노드를 찾아가는 과정이 빠르다
두 a안과 b안을 비교해보았을 때, skwed tree/graph의 경우를 고려한다면 b안이 더 효율적이다!
나의 풀이
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
nums = [i for i in range(N + 1)]
def find(n):
if nums[n] == n:
return n
else:
root = find(nums[n])
nums[n] = root
return nums[n]
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a == root_b:
return
if root_a > root_b:
nums[root_a] = root_b
# nums[a] = root_b # 틀린 코드
else:
nums[root_b] = root_a
# nums[b] = root_a # 틀린 코드
def is_union(a, b):
return find(a) == find(b)
for _ in range(M):
cmd, a, b = map(int, input().rstrip().split())
if cmd:
if is_union(a, b):
print("YES")
else:
print("NO")
else:
union(a, b)
find 함수
- 배열의 부모 값이 자신과 동일할 때, 루트 노드에 도달한 것임으로 알고 반환
- 배열의 부모 값이 자신과 동일하지 않으면, 배열의 부모 값을 재귀적으로 타고 올라가며 루트 노드 값을 가져오고 이를 자식노드의 배열 값에 저장하여 업데이트 한다
union 함수
- 두 노드를 합치기 위해서, 두 노드의 루트 노드 값을 가져온다
- 두 노드의 루트 노드 값이 동일하다면 서로 동일한 집합에 있는 것이므로 함수 종료
- 두 노드의 루트 노드 값이 다르다면, 루트 노드 값의 크기를 비교하여 큰 수가 작은 수를 가리키도록 한다 (작은 수가 루트가 된다는 뜻
- 여기서 중요한 것은 !!!!!!!!!!!!!!!! nums[a] = root_b이나 nums[b] = root_a가 아닌 nums[root_a] = root_b나 nums[root_b] = root_a로 바꾸어 주어야 한다
- 왜냐하면 이전 루트노드가 가리키는 값을 바꾸어주어야 하는데, 그 밑에 있는 노드가 가리키는 값을 바꾸게 된다면 이전 루트노드와의 연결이 끊기게 되기 때문!
is_union 함수
- 두 노드의 루트 노드 값을 가져온다
- 두 루트 노드 값을 비교하여 같은 집합인지 여부를 반환한다
그 외 유의할 것
- 재귀함수를 이용했기 때문에, 재귀가 깊어질 경우 런타임 에러 발생 -> sys.setrecursionlimit() 사용
- 시간초과 발생 방지를 위해서는 sys.stdin.readline 사용 권장!
참고 페이지
[알고리즘] 유니온 파인드 (Union-Find)
두 노드는 서로 같은 집합에 속할까?
velog.io
'Dev > BAEKJOON 백준' 카테고리의 다른 글
[백준/BOJ] 백준 코딩 알고리즘 2156번 포도주 시식 Python (다이나믹 프로그래밍) (0) | 2023.08.23 |
---|---|
[백준/BOJ] 백준 코딩 알고리즘 1976번 여행 가자 Python (유니온 파인드) (0) | 2023.08.22 |
[백준/BOJ] 백준 코딩 알고리즘 14889번 스타트와 링크 Python (0) | 2023.08.16 |
[백준/BOJ] 백준 코딩 알고리즘 11053번 가장 긴 증가하는 부분 수열 Python (1) | 2023.08.16 |
[백준/BOJ] 백준 코딩 알고리즘 2751번 수 정렬하기 2 Python (0) | 2023.08.14 |