[Python] 백준 1717 집합의 표현

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

1717번: 집합의 표현

 

문제 해결

- 집합을 어떻게 합칠 것인가? ( union 사용해야겠지...?)

- set.add() 사용 할 것인가? => 사용하면 좋은데 어떻게 일반적으로 표현을 할 것인가? ex) 1번집합 2번집합 합치면 뭐로 표현???

- 해결책 => 트리를 이용해 부모를 정하자 ! ex) 1번집합 2번집합 합치면 숫자 작은 1번집합이라고 하자!

 

CODE

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(a):
    if a == parent[a]:
        return a
    p = find(parent[a])
    parent[a] = p
    return parent[a]

# a가 속해있는 집합과 b가 속해 있는 집합 합치기
def union(a,b):
    a = find(a)
    b = find(b)
    if a==b:
        return
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
for _ in range(m):
    command = list(map(int, input().split()))
    if command[0] == 0:
        union(command[1], command[2])
    elif command[0] == 1:
        if find(command[1]) == find(command[2]):
            print("YES")
        else:
            print("NO")

 

부모를 찾는 과정(find() 함수)에서 재귀가 사용 되었으므로 sys.setrecursionlimit()가 필요했다!

트리를 생각을 하면 쉽지만 오랜만에 풀면 생각하기 어려운 문제라고 생각한다.