[개념/자료구조/파이썬] Disjoint Set, Union-Find 구조

부제) 크루스칼 알고리즘에 이용되는 자료구조

개념

• 두 집합 사이에 교집합 원소는 하나도 없고, 모든 집합의 합집합은 전체집합인 자료구조. 
• 수학으로 정의하면, 서로소 관계인 두 집합을 이야기한다.
• 컴퓨터에서는 파티션이 이러한 구조이다.(C,D,E드라이브들을 다 합치면, 하드디스크 용량이 나오는것처럼)
• MST를 찾는 크루스칼에 이용되는 자료구조이다.

구현(표현)

Union,Find 2가지 연산이 있으며, 각각의 트리(노드)들을 특이한 방식으로 1차원 배열에 mapping한다.

로또 아닙니다.

예시를 들어 보겠습니다. 8명이서 각자 조를 짜서, 여행을 간다고 생각해봅시다. 8명의 친구가 있고, 저는 "1"입니다.

• 저는 4명이 가는 여행이 가장 재밌다고 생각하여, 마음이 잘 맞는 2,3,4 친구와 함께 4명이서 가기로 했습니다.
• 4,5 친구는 둘이서 커플이여서 , 둘이서 가기로 하였습니다.
• 7,8 친구는 각자 혼자 여행을 하는게 좋아서, 각자 혼자 가기로 했습니다.

그렇다면, {1,2,3,4} , {4,5} , {7},{8} 4개의 여행 그룹이 나오게 됩니다. 

이러한 과정들을 컴퓨터에서 구현하려고 할때, 적절한 자료구조형이 바로 유니온 -파인드 자료구조 입니다.

그래서, 각 조의 번호가 제일 빠른사람이 조장을 맡기로 해서, 1차원 배열으로 아래와 같이 나타내기로 했습니다.

Parent[i]

• root Node를 value로 가지고 있다.
• Root Node는 Value로 자기자신을 가진다.
• 이렇게 정리해놓으면, 4번 친구는 1번 그룹에 속해있다는걸 바로 알 수 있고, 6,7친구들이 외로워서 1번그룹에 참여한다면, value 값을 0으로 바꾸기만 하면된다.

Find 연산

• 하나의 노드가 같은 RootNode를 공유하는지 확인하는 연산이다. 즉, 같은 그룹에 속해있는지 확인하는 절차이다.
• Root Node라면, 자기 자신을 반환한다.
• parent[target] = Find(parent[target])을 통해서, 경로를 압축한다.

def find(target):
	if target == parent[target]:
    	return target
    #경로 압축
	parent[target] = find(parent[target])
    return parent[target]

경로압축?

• 우리는 그룹을 그래프 관계로 다양하게 나타낼 수 있지만, 접근성을 위해서 오른쪽과 같이 나타내는게 제일 효율적이다. 그래서, 만약 root Node를 타고 올라간다면, 최종 루트노트옆에 바로 붙여주는 개념으로 구현한다.

Union연산

• 두 그룹을 하나의 그룹으로 만드는 연산이다. 
• 먼저, 두 트리가 같은 루트를 공유하는지 확인하고, 같은 루트를 공유하지 않는다면, 둘을 합쳐준다.
• 이때, 트리의 사이즈를 고려해서, 트리를 붙이거나 뗄 수도 있고, 다양한 기법이 들어갈 수도 있지만, 여기서는 간편하게 번호가 앞서는 곳에 붙이도록 구현하겠음!

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

전체코드

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

N=int(input())
parent=[x for x in range(N+1)]

def find(target):
    if target==parent[target]:
        return target
    #경로 압축
    parent[target] = find(parent[target])
    return parent[target]

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