백준 / 1717번 / 집합의 표현 / python 파이썬

 

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

 

예제 입력 1 

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력 1 

NO
NO
YES

---

나의 풀이

n, m = map(int, input().split())

parent = [i for i in range(n+1)]

def find(a):
    if parent[a] == a:
        return a
    parent[a] = find(parent[a])
    return parent[a]

def union(a,b):
    a, b = find(a), find(b)
    if a == b: return
    parent[a] = b

def check(a,b):
    if parent[a] == parent[b] or find(a) == find(b):
        return "YES"
    return "NO"

for _ in range(m):
    num, a, b = map(int, input().split())
    if num:
        print(check(a, b))
    else:
        union(a,b)

 

집합을 사용하여 풀면 시간초과가 발생한다. 따라서 Union-Find 알고리즘을 사용하여 풀어야 한다. 

Union-Find 알고리즘은 주로 집합을 합치고, 두 원소가 같은 집합에 속하는지 확인한느 문제를 해결하는데 사용된다.

 

 

• Union: 두 개의 원소를 하나의 집합으로 합친다.
• Find: 주어진 원소가 속한 집합의 대표(루트) 원소를 찾는다.
• 경로 압축 (Path Compression): find 연산을 효율적으로 만들어주는 기법으로, 찾은 루트를 부모로 바로 연결하여 이후 연산을 더 빠르게 할 수 있도록 한다.
• 합치기(Union by Rank): 여러 집합을 합칠 때, 더 작은 집합을 더 큰 집합에 합쳐서 트리 구조의 깊이를 최소화하는 기법이다.(이 코드에서는 사용하지 않았지만, 보통 성능 최적화에 유용함)

 

서로소 집합 알고리즘