BaekJoon 1717번 : 집합의 표현 (python)

BaekJoon 1717번 : 집합의 표현 (G5 28.095%)

집합의 표현 문제

Union-Find 알고리즘을 이용한 문제이다.

Union-Find 알고리즘은 그래프에서 서로소 집합(Disjoint Set)을 관리하기 위한 자료구조이다.
이 알고리즘은 주로 네트워크 연결, 최소 신장 트리, 그룹 구분 등 여러 분야에서 활용된다.

• Union: 두 원소가 속한 집합을 합친다.
• Find: 원소가 속한 집합의 대표자(루트)를 찾는다.

Union-Find 알고리즘을 효율적으로 관리하기 위한 두 가지 기법이 존재한다.

• 경로 압축(Path Compression): Find 함수를 실행하는 동안 만나는 모든 노드를 직접 루트에 연결하여 트리의 높이를 낮춘다. 이는 후속 연산의 속도를 향상시킨다.
• 합병 순위(Union by Rank): 두 트리를 합칠 때, 높이가 더 낮은 트리를 높이가 더 높은 트리 아래에 붙인다. 이렇게 함으로써 트리의 높이가 최소한으로 증가하도록 관리한다.

• 해당 문제에서는 a에서 0이 주어질 때 b와 c를 합치는 과정 즉, union(b,c)를 진행하고 1이 주어졌을 때는 해당 노드가 연결되어있는지 즉, find(b) == find(c)를 통해 두 노드의 루트 노드가 같은지 체크해준다.

---

import sys
input = sys.stdin.readline

def find(x) :
    if root[x] != x :
        root[x] = find(root[x])
    return root[x]

def union(x,y) :
    rootx = find(x)
    rooty = find(y)

    if rootx != rooty :
        if rank[rootx] > rank[rooty] :
            root[rooty] = rootx
        elif rank[rootx] < rank[rooty] :
            root[rootx] = rooty
        else :
            root[rooty] = rootx
            rank[rootx] += 1

n, m = map(int,input().split())
rank = [1] *(n+1)
root = list(range(n+1))

for _ in range(m) :
    a, b, c = map(int,input().split())
    if a == 1:
        if find(b) == find(c) :
            print('YES')
        else :
            print('NO')
    else :
        union(b,c)