[백준/BOJ] 백준 코딩 알고리즘 1717번 집합의 표현 Python (유니온 파인드)

 

유니온 파인드란?

유니온 파인드: 두 노드가 같은 집합에 속하는지 판별하는 알고리즘

→ 유니온 : 두 노드를 합치는 연산

→ 파인드: 두 노드의 루트 노드를 찾는 연산

 

 

파인드 연산에서 고려해볼 것

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 사용 권장!

 

 

참고 페이지

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Union-Find

[알고리즘] 유니온 파인드 (Union-Find)