백준 1717번: 집합의 표현

문제

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

해설

서로소 집합(disjoint sets)을 활용하는 문제이다. 서로소 집합 자료구조는 합집합(union)과 찾기(find) 연산으로 구성된다.

찾기 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 코드에서는 부모 노드가 몇번인지 연산하여 부모 원소 번호를 반환한다. 만약 두 원소가 같은 부모 원소 번호를 갖고 있으면 두 원소는 같은 집합이라고 생각할 수 있다.

합집합 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. 이 때 찾기 연산을 사용하여 두 원소의 부모 원소 번호를 비교하고 더 작은 부모 원소로 통일한다.

※ 주의할 점

Python으로 풀 경우 재귀 깊이 제한을 풀어줘야 한다. 그렇지 않으면 런타임 에러가 발생 😂

n의 크기가 최대 백만이니 recursion limit을 1000000으로 설정하여 해결했다.

Python은 기본 세팅된 재귀 깊이가 작은 편이니 재귀를 사용하는 문제는 이 점을 늘 유의!

코드(Python)

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

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

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

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for _ in range(m):
    opr, a, b = map(int, input().split())
    if opr == 0:
        union_parent(a, b)
    elif opr == 1:
        if find_parent(a) == find_parent(b):
            sys.stdout.write("YES\n")
        else:
            sys.stdout.write("NO\n")