Union-Find 알고리즘이란?

Disjoint Set(서로소 집합)을 표현할 때 사용하며, 2가지 주요 연산인 Union과 Find를 이용하는 알고리즘이다.
Union-Find 알고리즘이란?
Contents
Union-Find 알고리즘 소개
Tree 구조
시간복잡도
공간복잡도
프로그래머스 네트워크 문제로 살펴보는 Union-Find 알고리즘

Union-Find 알고리즘 소개

Union-Find 알고리즘은 Disjoint Set(서로소 집합)을 표현할 때 사용하는 알고리즘이다. 이 알고리즘은 두 가지 주요 연산, 즉 "Union"과 "Find"를 제공한다.

  1. Union: 두 개의 원소가 속한 집합을 하나로 합친다. 이 연산은 두 집합이 서로 다른 집합에 속해 있을 때만 수행된다.

  2. Find: 주어진 원소가 속한 집합을 반환한다. 이 연산은 주어진 원소의 "대표자" 또는 "루트"를 찾는 데 사용된다.

두 집합이 공통의 원소를 가지지 않을 때, 이들을 서로소 집합이라고 한다. 즉, 두 집합의 교집합은 공집합이다. 서로소 집합 데이터 구조는 중첩되지 않는, 즉 서로소인 원소의 부분집합을 저장하는 데이터 구조다.

  • 새로운 집합을 서로소 집합에 추가하는 연산

  • 서로소 집합을 하나의 집합으로 합치는 Union 연산

  • 서로소 집합의 대표를 찾는 Find 연산

  • 두 집합이 서로소인지 확인하는 연산

예를 들어, 여러 사람들이 있고 다음과 같은 작업을 수행해야 하는 상황을 생각해보세요:

  • 새로운 친구 관계를 추가하는 작업, 즉 사람 x가 다른 사람 y의 친구가 되는 것.
    이는 새 원소를 집합에 추가하는 것에 해당합니다.

  • 개인 x가 개인 y의 친구인지 (직접적이든 간접적이든) 확인하는 작업

이러한 작업들은 서로소 집합 데이터 구조와 Union, Find 연산을 통해 효과적으로 수행될 수 있습니다.

Tree 구조

Union-Find 알고리즘은 트리 구조를 사용하여 집합을 표현한다. 여기서 각 노드는 원소를, 트리는 집합을 나타낸다. 트리의 루트 노드는 해당 집합의 대표자를 나타낸다.

Union 연산은 두 트리의 루트 노드를 연결하여 두 집합을 하나로 합치고 Find 연산은 주어진 노드의 루트 노드를 찾는다. 이 루트 노드는 해당 노드가 속한 집합의 대표자를 나타낸다.

Union-Find 알고리즘은 그래프에서 연결 요소를 찾거나, 두 노드가 같은 집합에 속해 있는지를 빠르게 확인하는 등의 문제를 효율적으로 해결할 수 있다.

시간복잡도

n개의 단일 항목 집합을 생성하는 데 O(n)이다. 두 가지 기법 - 경로 압축과 랭크/크기에 의한 합집합(union)을 사용하면, 시간 복잡도는 거의 상수 시간에 도달한다.

결과적으로, 최종적인 평균 시간 복잡도는 O(α(n))이며, 여기서 α(n)은 역 아커만 함수로, 매우 안정적으로 증가한다 (n<10600인 경우에도 넘지 않습니다).

(α(n)은 아주 천천히 증가하는 함수)

공간복잡도

O(n)이다. 이는 우리가 서로소 집합 데이터 구조에 n개의 원소를 저장해야 하기 때문이다. 원소가 많아질수록 저장 공간이 더 필요하다는 것을 의미한다.

프로그래머스 네트워크 문제로 살펴보는 Union-Find 알고리즘

[문제설명]

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

[제한사항]

  • 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.

  • 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.

  • i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.

  • computer[i][i]는 항상 1입니다.

[Python3 풀이]

def solution(n, computers):
    parent = list(range(n)) # 각 노드의 부모 노드를 저장하는 리스트(초기에 자기자신이 부모 노드)

    # 주어진 노드의 부모 노드를 찾는 함수
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    # 두 노드의 루트 노드가 다르면 두 노드를 연결하는 함수
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x != root_y:
            parent[root_y] = root_x

    # 모든 노드를 순회하며 두 노드를 연결하는 함수를 호출
    for i in range(n):
        for j in range(n): 
            if computers[i][j] == 1:
                union(i, j)

    for i in range(n):
        find(i)
    
    return len(set(parent))

🐣 : 프로그래머스 문제 풀다가 이 문제를 만났는데 DFS, BFS 문제라고 하던데, 다른 방법으로 풀고 싶어서 코파일럿한테 물어봤는데 다음과 같이 답해줬음.

네트워크의 개수를 찾는 문제는 그래프의 연결 요소(Connected Component)를 찾는 문제로 볼 수 있습니다. 이 문제를 해결하는 데는 여러 가지 알고리즘이 있습니다

깊이 우선 탐색 (DFS): 이미 코드에서 사용된 방법입니다. 시작 노드에서 시작하여 아직 방문하지 않은 인접 노드를 재귀적으로 방문합니다.

너비 우선 탐색 (BFS): 시작 노드에서 시작하여 아직 방문하지 않은 모든 인접 노드를 큐에 넣고 방문합니다. 이 방법은 DFS와 비슷하지만, DFS가 재귀를 사용하는 반면 BFS는 큐를 사용합니다.

이산 구조 (Disjoint Set): 이 방법은 Union-Find 알고리즘을 사용하여 각 노드가 어떤 집합에 속하는지를 관리합니다. 두 노드가 같은 집합에 속하면 같은 네트워크에 속하고, 그렇지 않으면 다른 네트워크에 속합니다.

플로이드-워셜 알고리즘: 이 방법은 모든 노드 쌍 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘을 사용하여 각 노드 쌍이 연결되어 있는지 확인하고, 연결되어 있지 않은 노드 쌍이 있으면 다른 네트워크에 속한다고 판단할 수 있습니다.

🐣 : DFS, BFS는 다른 문제 풀면서 시도해봤는데, 이산구조랑 플로이드-워셜 알고리즘으로 푼 적이 없어서 구글링하다가 풀었다. 코파일럿이 풀어줬지만 이걸 보고 이해하는데 하루가 걸린 듯하다... 그러다가 좋은 사이트 발견!! GeeksforGeeks 공부하기 좋은 것 같다!



(혹시 사실과 다른 부분이 있다면 알려주십쇼)

Share article
RSSPowered by inblog