[#1717] 집합의 표현

❓ Question

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

📖 Before Start

Union - Find 알고리즘을 사용한 분리 집합 문제를 풀어보자.

이번 문제는 Union-Find 알고리즘을 활용한 분리 집합 개념을 활용했다.
Union - Find 의 기본 개념과도 같은 문제이기에 정리를 하고자 한다.

✒️ Design Algorithm

Union 연산을 진행할지, Find 연산을 진행할지 구별하자.

첫번째 줄에는 원소의 갯수 N 과 연산의 수량 M 이 한 줄에 걸쳐 입력된다.
그 후 M 줄에 걸쳐 연산이 진행되는데, 크게 합집합 과 동일 집합 확인 으로 나뉜다.

합집합 연산의 경우 0 으로 시작되며, 두 숫자를 하나의 집합으로 묶는다.
동일 집합 확인의 경우 1 로 시작되며, 두 숫자가 동일한 집합에 있는지 체크한다.

상당히 전형적인 분리 집합 문제이다. 바로 코드를 작성했다.

💻 Making Own Code

✅ Correct Code

import sys
sys.setrecursionlimit(10 ** 6)

read = sys.stdin.readline
N, M = map(int, read().split())
parent = list(range(N + 1))

def find(x):
    # 루트 노드를 찾지 못했으면, 경로를 압축하여 재귀 진행.
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

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

for _ in range(M):
    is_union, a, b = list(map(int, read().split()))
    if is_union:
        print('YES' if find(a) == find(b) else 'NO')
    else:
        union(a, b)

Union - Find 연산을 통해 분리 집합 문제를 풀 수 있다.

결국 문제에서 요구하는 사항을 정직하게 수행하면 쉽게 풀 수 있다.
다만 여기서 경로 압축 이라는 개념이 생소하여 개인적인 공부를 진행하였다.

기존의 Find 연산을 위한 함수는 아래와 같이 작성하였다.

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

파라미터로 받은 x 의 루트 노드가 자기 자신이라면 이를 return 시키고,
그렇지 않을 경우 재귀 호출을 통해 상위 노드를 종료 시까지 계속 탐색한다.

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

하지만 경로 압축을 진행하면 보다 효율적으로 find 연산이 가능해진다.
자세한 설명은 https://bowbowbow.tistory.com/26 에서 열람하면 좋다.
차이점은 parent 배열을 통해 찾아낸 루트 노드를 업데이트 하는 것이다.

📖 Conclusion

📒 github Code link

https://github.com/RookieAND/BaekJoonCode