[Python] 1717 - 집합의 표현

[Gold V] 집합의 표현 - 1717 

[문제 링크](https://www.acmicpc.net/problem/1717)

🗝️알고리즘 분류

• 자료 구조
• 분리집합

---

💻문제 정의

초기에 n+1 개의 집합이 주어졌을 때, 합집합 연산과 두 원소가 같은 집합에 속하는 지를 확인하는 연산 두 가지의 연산이 주어질 때, 집합을 표현하는 프로그램을 작성하는 문제이다.

 

💡접근 및 설계

합집합 연산이 주어지면 집합을 병합한다.(Union) 이후 두 개의 원소가 주어졌을 때 두 원소가 같은 집합에 존재하는지 여부를 YES or NO로 답해야 한다.

 

결국 두 원소가 주어졌을 때, 두 원소가 속해있는 집합이 서로소 관계에 있는지, 즉 분리 집합인지를 판단하여 결과를 반환하여 문제를 해결할 수 있다.

 

분리 집합 문제를 해결하기 위해 Union-Find 알고리즘을 이용하였다.

 

✏️알고리즘 풀이

Union-Find를 구현하기 위해 일반적으로 트리 구조의 자료구조를 이용한다. 트리 구조는 반드시 루트노드가 존재한다. 우리는 두 개의 원소가 주어졌을 때, 해당 원소가 속해있는 트리의 루트 노드를 비교하여 같은 트리, 즉 같은 집합에 존재하는지를 판별한다.

 

def find_root(x):
    if (parent[x] == x): return x
    parent[x] = find_root(parent[x])
    return parent[x]

def same_root(a, b):
    return find_root(a) == find_root(b)

def union_set(a, b):
    x = find_root(a)
    y = find_root(b)
    if (x > y):
        parent[x] = y 
    else: 
        parent[y] = x

find_root() : 해당 원소의 루트 노드를 반환하는 함수. parent 리스트에 각 원소별로 루트 노드가 저장된다.

same_root() : 두 원소의 루트 노드가 같은지를 비교

union_set() : 두 원소가 속한 집합을 병합(Union 연산)

 

 

🗒️제출 코드

# 1717 집합의 표현

import sys
sys.setrecursionlimit(1000000)

def find_root(x):
    if (parent[x] == x): return x
    parent[x] = find_root(parent[x])
    return parent[x]

def same_root(a, b):
    return find_root(a) == find_root(b)

def union_set(a, b):
    x = find_root(a)
    y = find_root(b)
    if (x > y):
        parent[x] = y 
    else: 
        parent[y] = x

N, M = map(int, input().split())

parent = [i for i in range(N+1)]
for _ in range(M):
    cmd, a, b = map(int, input().split())

    if (cmd == 0):
        union_set(a, b)

    elif (cmd == 1):
        print("YES") if same_root(a, b) else print("NO")

---

💭오늘의 회고

분리 집합이라는 새로운 자료 구조에 대해 공부하게 되었다.

이전에 최소 스패닝 트리 관련 문제를 풀면서 Union-Find에 대한 개념을 잠깐 공부하였으나, 그 당시에는 이해하지 못하였다.

 

하지만 분리집합이라는 개념과 함께 문제를 해결하며 접근하였더니 얼추 동작 원리는 이해가 되었다.

 

또 다른 문제를 풀어보며 해당 개념을 응용할 수 있도록 해보자...!