[BOJ] 1717번 : 집합의 표현

🔒 문제

⌨ 입력

🖨 출력

📍 제한

📚 예제

📌 풀이

이 문제는 union-find의 기본 문제가 아닐까 싶다.
그냥 보자마자 어,, union-find다 라는 생각이 들었다.

문제를 푸는 것 자체는 안어려웠지만, error가 많이 나서 보니까

1. Recursive error

이 오류는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어져서 발생한다.

sys.setrecursionlimit(10**6)

을 사용해서 Python이 정한 최대 재귀 깊이를 변경해서 풀어준다.

2. memory 초과

이건 pypy로 했더니 발생했다.
해결법은 딱히 찾지 못했다.

3. 시간초과

root 함수를 짤 때 처음엔 root를 찾기만 했지, 찾으면서 root값들을 변경해주는 것이 없었다.
그래서 root를 찾을때마다 연산 수 가 많아져서 발생한 오류이다.
따라서 root를 찾을 때, root 값들을 갱신해주니까 오류가 사라졌다.

# 수정 전 코드
def root(t):
    if Set[t] == t:
        return t
    return root(Set[t])

# 수정 후 코드
def root(t):
    if Set[t] == t:
        return t
    # 시간초과 안뜨려면 root 찾을 때 root 바로바로 업데이트 해서 tree 깊이 낮추기
    r = root(Set[t])
    Set[t] = r
    return Set[t]

🔑 python 코드

# 집합의 표현
import sys
sys.setrecursionlimit(10**6) # 파이썬 Recursion Error 피하려고
input = sys.stdin.readline
n, m = map(int, input().split())
Set = [i for i in range(n + 1)]

def root(t):
    if Set[t] == t:
        return t
    # 시간초과 안뜨려면 root 찾을 때 root 바로바로 업데이트 해서 tree 깊이 낮추기
    r = root(Set[t])
    Set[t] = r
    return Set[t]

def union(a, b):
    r1 = root(a)
    r2 = root(b)

    if r1 == r2:
        return
    elif r1 > r2:
        Set[r1] = r2
    elif r2 > r1:
        Set[r2] = r1

for _ in range(m):
    op, a, b = map(int, input().split())
    if op == 0: # 합집합
        union(a, b)
    else: # 같은 집합인지 확인하기
        if(root(a) == root(b)):
            print("yes")
        else:
            print("no")