직전에 푼 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 공식 설명을 살펴보자!
백준 채점 서버에서 Python의 최대 재귀 깊이는 1,000으로 설정되어 있다. RecursionError가 생기는 이유는 대부분 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때!
📌 해결:
sys.setrecursionlimit()
을 사용해서 최대 재귀 깊이를 늘려주자!
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline