[PS] BOJ 1717 집합의 표현

문제 링크

---

직전에 푼 20040 사이클 게임과 비슷한 문제로, 유니온파인드로 풀면 된다.

유니온파인드를 구현한 후 0으로 시작하는 입력과 1로 시작하는 입력을 나눠, 전자의 경우엔 노드를 합지고(union) 후자의 경우엔 루트 노드가 같은지(find) 비교하면 된다.

이 문제에서 계속 RecursionError가 발생했는데 그 이유는 아래에 정리했다.

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n, m = map(int, input().split())
parent = list(range(n + 1))

def find_parent(x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]
    
def union(a, b):
    a = find_parent(a)
    b = find_parent(b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
for _ in range(m):
    num, a, b = map(int, input().split())
    if num == 0:
        union(a, b)
    else:
        if find_parent(a) == find_parent(b):
            print('YES')
        else:
            print('NO')

---

런타임 에러 (RecursionError)가 생긴 이유

백준 RecursionError 공식 설명을 살펴보자!

백준 채점 서버에서 Python의 최대 재귀 깊이는 1,000으로 설정되어 있다. RecursionError가 생기는 이유는 대부분 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때!

📌 해결: sys.setrecursionlimit()을 사용해서 최대 재귀 깊이를 늘려주자!

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline