[BOJ] 1717 - 집합의 표현

1717번: 집합의 표현

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

문제 정의

---

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

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

접근 방법

---

0이면 두 원소를 합하고, 1이면 두 원소가 같은 집합인지 확인하므로, 유니온파인드 자료구조를 활용할 수 있다.

문제 해설

---

• 집합의 각 원소에 대한 부모 노드를 초기화 한다. 처음에는 각 원소가 부모노드가 된다.

• 입력에 따라 0이면 두 원소를 합한다. 이 때 부모의 노드를 찾아서 작은 쪽의 노드가 큰 쪽의 부모가 되게끔 부모노드를 업데이트 해주면 된다.

• 1이면 두 원소의 부모노드를 찾아서 같다면 YES, 다르다면 NO를 출력한다.

풀이

---

• 재귀 깊이에 유의한다.

# 유니온파인드
import sys
sys.setrecursionlimit(1000000) # 재귀 깊이 제한 늘리기
# sys.setrecursionlimit(10**6) # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

n, m = map(int, input().split())    # n+1개의 집합, m개의 연산
parent = [0] * (n+1)    # (n+1)개의 부모 노드 리스트

# 부모 테이블 자기 자신으로 초기화
for i in range(n+1):
    parent[i] = i
    
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for _ in range(m):
    check, a, b = map(int, input().split())
    if check == 0:
        # a, b를 합치고
        union_parent(parent, a, b)
    else:
        # a, b가 같은 집합에 포함되어 있는지 확인한다.
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')

정리

---

• 유니온 파인드 개념을 활용해볼 수 있는 좋은 문제였다.

Uploaded by N2T