1717 - 집합의 표현

정보

• 문제 보기: 1717 - 집합의 표현
• 소요 시간: 40분 18초
• 풀이 언어: python
• 체감 난이도: 3️⃣~4️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

유니온파인드

풀이 코드

정보

• 메모리: 78276 KB
• 시간: 296 ms

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

n, m = 0, 0
parent = []

def find(t): # find t's root (t: target)
    global parent
    
    if t == parent[t]: # base case
        return t
    
    root = find(parent[t])
    parent[t] = root
    
    return root

def union(t1, t2):
    global parent
    
    r1 = find(t1)
    r2 = find(t2)
    
    if r1 == r2:
        return # same set
    elif r1 < r2:
        parent[r2] = r1
    else:
        parent[r1] = r2

def solution():
    global n, m, parent
    
    n, m = map(int, input().split())
    parent = [i for i in range(n+1)] # init
    
    for _ in range(m):
        op, t1, t2 = map(int, input().split())
        
        if op == 0:
            union(t1, t2)
        elif op == 1:
            print('YES' if find(t1) == find(t2) else 'NO')
    

if __name__ == '__main__':
    solution()

풀이 해설

if r1 == r2:
    return # same set
elif r1 < r2:
    parent[r2] = r1 # 더 작은 노드 값으로 루트 지정
else:
    parent[r1] = r2 # 더 작은 노드 값으로 루트 지정

더 작은 노드 값을 parent에 저장하는데, 이 레퍼런스처럼 큰 값을 기준으로 저장해도 된다.

어느 쪽이든 집합을 대표하는 루트 노드 값을 지정해주면 된다.

✨Diagram

(인덱스 편의 상 parent[0]은 그냥 공란으로 두고 구현함)

메모

처음에 유니온 파인드 이해가 부족해서 parent[t2] = r1 식으로 구현했는데 이는 WA이다.

집합을 대표하는 루트 노드의 값을 기준으로 처리해야 하기 때문이다.

참고