집합의 표현 ( 1717 번 )

1717번: 집합의 표현

 

---

🧠 알고리즘

• 유니온 파인드 (Union-Find / Disjoint Set Union, DSU)

 

✔️ 동작 방식

문제 핵심 아이디어:

• 서로소 집합을 관리하며, 두 원소가 같은 집합에 속하는지 확인하거나(find) 두 집합을 합치는(union) 문제에 사용.

1. 초기화:
   • pt_list[i] = i로 각 원소를 자기 자신이 부모가 되도록 설정.
2. find 연산 (_find_pt):
   • 특정 원소가 속한 집합의 대표자를 찾음.
   • 경로 압축(Path Compression) 사용: 탐색 과정에서 만나는 모든 원소의 부모를 대표자로 바로 갱신하여 이후 연산을 빠르게 함.
   • 반복문 기반 구현으로 재귀 깊이 초과 문제 방지.
3. union 연산 (_union):
   • 두 원소가 속한 집합을 합침.
   • 대표자 비교 후 작은 쪽으로 부모를 갱신.
   • 이렇게 하면 트리의 높이를 얕게 유지 가능.
4. 연산 처리 (_main):
   • 입력으로 주어진 m개의 연산을 순차 처리.
   • type == 0: 두 원소를 같은 집합으로 합침 (_union)
   • type == 1: 두 원소가 같은 집합인지 확인 (_find_pt)
   • 결과를 YES 또는 NO로 리스트에 저장 후 한 번에 출력.

---

 

🧾 코드

import sys

def _find_pt(num):
    while pt_list[num] != num:
        pt_list[num] = pt_list[pt_list[num]]  # 경로 압축
        num = pt_list[num]
    return pt_list[num]


def _union(x, y):
    x_root, y_root = _find_pt(x), _find_pt(y)
    if x_root > y_root:
        pt_list[x_root] = y_root
    else:
        pt_list[y_root] = x_root
        

def _main(n, m):
    answer = []
    for _ in range(m):
        type, a, b = map(int, sys.stdin.readline().rstrip().split())
        a_root, b_root = _find_pt(a), _find_pt(b)
        
        if type == 0: # 합치기
            _union(a_root, b_root)
        else:
            answer.append("YES") if a_root == b_root else answer.append("NO")

    return '\n'.join(answer)


n, m = map(int, sys.stdin.readline().rstrip().split())
pt_list = [i for i in range(n + 1)]
print(_main(n, m))

---

 

⏱️ 시간 복잡도

for _ in range(m) : m번 순회 ( 선형 시간 복잡도 )
	# 유니온 파인드 - 경로 압축 시간 연산 ( 상수 시간 )
    _find_pt(num)
    _union(x, y)
    
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )