[Algorithm] Union-Find (합집합 찾기)

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12347

알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지

 

 

인프런 알고리즘 강의 18강에 대한 리뷰다.

 

 

union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.

 

find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

 

union-find 자료구조는 다른말로 서로소 집합(Disjoint Sets) 자료구조라고도 불린다.

* 서로소 집합은 공통 원소가 없는 두 집합을 의미한다.

 

 

union-find는 보통 트리 자료구조를 이용하여 집합을 표현한다.

 

 

 

 

union 연산의 알고리즘은 다음과 같다.

 

1. union 연산을 확인하여 서로 연결된 두 노드 A, B를 확인한다.
   • A와 B의 루트 노드를 찾는다
   • 재귀적으로 부모 노드를 찾아 루트 노드를 찾는다. (A`, B`)
   • B`가 A`를 부모 노드로 설정하게 한다. (B`가 A`를 가리키도록 한다.)
     • (대개 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 한다.)
2. 모든 union 연산을 처리할 때까지 1의 과정을 반복한다.

 

 

 

 

** C++

 

 

#include <stdio.h>

// 재귀적으로 부모 노드를 찾음 
int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
	return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수
int unionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

// 같은 부모인지 확인하는 함수
int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) return 1;
	return 0;
}

int main(void) {
	int parent[11]; // 부모 테이블 초기화
	for (int i = 1; i <= 10; i++) {
		parent[i] = i; // 자기 자신을 부모로 가지도록 설정
	}
	unionParent(parent, 1, 2);
	unionParent(parent, 2, 3);
	unionParent(parent, 3, 4);
	unionParent(parent, 5, 6);
	unionParent(parent, 6, 7);
	unionParent(parent, 7, 8);
	printf("1과 5는연결되어 있나요? %d\n", findParent(parent, 1, 5));
	unionParent(parent, 1, 6); // 1 -  5, 6, 7 / 2 - 8
	printf("1과 5는연결되어 있나요? %d\n", findParent(parent, 1, 5));
}

 

 

 

** Javascript

 

 

// 재귀적으로 부모 노드를 찾음 
function getParent(parent, x) {
	if (parent[x] == x) return x;
	return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수
function unionParent(parent, a, b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b) parent[b] = a
	else parent[a] = b;
}

// 같은 부모인지 확인하는 함수
function findParent(parent, a, b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) return "true";
	return "false";
}

function main() {
	let parent = [0];
	for (let i = 1; i <= 10; i++) {
		parent.push(i);
	}
	unionParent(parent, 1, 2);
	unionParent(parent, 2, 3);
	unionParent(parent, 3, 4);
	unionParent(parent, 5, 6);
	unionParent(parent, 6, 7);
	unionParent(parent, 7, 8);
	console.log(`1과 5는연결되어 있나요? ${findParent(parent, 1, 5)}`);
	unionParent(parent, 1, 6); // 1 -  5, 6, 7 / 2 - 8
	console.log(`1과 5는연결되어 있나요? ${findParent(parent, 1, 5)}`);
}

main();

 

 

** Java

 

public class Main
{
    private static int getParent(int[] parent, int x) {
        if (parent[x] == x) return x;
        return parent[x] = getParent(parent, parent[x]);
    }
    
    private static void unionParent(int[] parent, int a, int b) {
        a = getParent(parent, a);
        b = getParent(parent, b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }
    
    private static String findParent(int[] parent, int a, int b) {
        a = getParent(parent, a);
        b = getParent(parent, b);
        if (a == b) return "true";
        return "false";
    }
    
	public static void main(String[] args) {
	    int[] parent = new int[11];
	    for (int i = 1; i <= 10; i++) {
	        parent[i] = i;
	    }
	    unionParent(parent, 1, 2);
	    unionParent(parent, 2, 3);
	    unionParent(parent, 3, 4);
	    unionParent(parent, 5, 6);
	    unionParent(parent, 6, 7);
	    unionParent(parent, 7, 8);
	    System.out.printf("1과 5는연결되어 있나요? %s\n", findParent(parent, 1, 5));
	    unionParent(parent, 1, 6); // 1 -  5, 6, 7 / 2 - 8
	    System.out.printf("1과 5는연결되어 있나요? %s\n", findParent(parent, 1, 5));
	}
}

 

 

 

 

** Python

 

def getParent(parent, x):
    return parent[x] if parent[x] == x else getParent(parent, parent[x])

def unionParent(parent, a, b):
    a = getParent(parent, a)
    b = getParent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def findParent(parent, a, b):
    a = getParent(parent, a)
    b = getParent(parent, b)
    return "true" if a == b else "false"
    
def main() :
    parent = [0]
    for i in range(1, 11):
        parent.append(i)
    unionParent(parent, 1, 2)
    unionParent(parent, 2, 3)
    unionParent(parent, 3, 4)
    unionParent(parent, 5, 6)
    unionParent(parent, 6, 7)
    unionParent(parent, 7, 8)
    print(f'1과 5는 연결되어 있나요? {findParent(parent, 1, 5)}')
    # unionParent(parent, 2, 8)
    print(f'1과 5는 연결되어 있나요? {findParent(parent, 1, 5)}')
    
if __name__ == "__main__":
    # execute only if run as a script
    main()

 

 

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

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def has_same_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    return "true" if a == b else "false"
    
def main() :
    v, e = map(int, input().split())
    parent = [0] * (v + 1) # 부모 테이블 초기화
    for i in range(1, v + 1):
        parent[i] = i # 부모 노드를 자기 자신으로 초기화
    
    # union 연산 수행
    for i in range(e):
        a, b = map(int, input().split())
        union_parent(parent, a, b)
    
    # 각 원소가 속한 집합 출력
    print("각 원소가 속한 집합: ")
    for i in range(1, v + 1):
        print(find_parent(parent, i))
    print()
    
    # 부모 테이블 내용 출력
    print("부모테이블: ")
    for i in range(1, v + 1):
        print(parent[i])
    
if __name__ == "__main__":
    # execute only if run as a script
    main()