[BOJ/Python] 1717. 집합의 표현

📌 문제

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

1717번: 집합의 표현

 

📌 문제 접근 방법

1. 상호배타 집합의 find_set연산과 union연산을 구현해서 풀이하였다.
2. 시간초과가 났는데, 해결을 위해서 재귀 깊이를 설정해주고 input을 sys.stdin.readline으로 바꿔줬다.
3. 최대 재귀 깊이는 어떻게 계산해야 하는지 궁금해졌다!
   지금까지는 아무거나 큰 값으로 넣어줬는데 어떻게 계산해야하지?

 

📌 코드

# 백준 1717 집합의 표현
import sys
sys.setrecursionlimit(9999999) # 재귀 깊이를 어떻게 계산?
input = sys.stdin.readline

def find_set(x):
    if x != parents[x]:
        parents[x] = find_set(parents[x])

    return parents[x]


def union(x, y):
    root_x = find_set(x)
    root_y = find_set(y)

    if rank[root_x] >= rank[root_y]:
        parents[root_y] = root_x
        if rank[root_x] == rank[root_y]:
            rank[root_x] += 1
    else:
        parents[root_x] = root_y


n, m = map(int, input().split())
parents = [x for x in range(n+1)]
rank = [0 for _ in range(n+1)]

for _ in range(m):
    command, a, b = map(int, input().split())

    if command:
        if find_set(a) == find_set(b):
            print('YES')
        else:
            print('NO')
    else:
        union(a, b)