Union-Find 알고리즘이란?
Union-Find 알고리즘 소개
Union-Find 알고리즘은 Disjoint Set(서로소 집합)을 표현할 때 사용하는 알고리즘이다. 이 알고리즘은 두 가지 주요 연산, 즉 "Union"과 "Find"를 제공한다.
Union: 두 개의 원소가 속한 집합을 하나로 합친다. 이 연산은 두 집합이 서로 다른 집합에 속해 있을 때만 수행된다.
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 공부하기 좋은 것 같다!
(혹시 사실과 다른 부분이 있다면 알려주십쇼)