[백준] 1717. 집합의 표현/Python - Gold5

❓문제

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

성능 요약

메모리: 77876 KB, 시간: 284 ms

분류

자료 구조, 분리 집합

문제 설명

초기에 n+1n+1개의 집합 {0},{1},{2},…,{n}{0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

✍🏻풀이

https://yoongrammer.tistory.com/102

서로소 집합(Disjoint Set) & 유니온 파인드(Union find)

위 사이트를 참고하여 구현했습니다.

💻코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
parent = [i for i in range(n + 1)]


def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]


def union(a, b):
    a, b = find(a), find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a


for _ in range(m):
    c, a, b = map(int, input().split())
    if c == 0:
        union(a, b)
    else:
        print("NO" if find(a) != find(b) else "YES")

📍후기

최대 깊이가 1000이라서 깊이를 바꾸지 않으면 에러가 난다. 그런데 PyPy3는 깊이를 바꾸면 메모리 초과가 발생해서 결국 Python3로 하게 되었다. 삼성은 PyPy3로 채점하는 데 그럼 이런 경우에는 어떻게 해야 할까...