union-find 알고리즘을 알아보자! in Pytho

 

 

1. 그래프  자료구조

union-find 알고리즘은 그래프 자료구조형에서 적용된다. 그래프의 구현방법은 2가지 방식이 존재한다

1) 인접행렬 (Adjacency Matrix) : 2차원 배열을 사용하는 방식

공간복잡도: 노드의 개수가 V, 간선의 개수가 E인 그래프가 있을 때, 인접행렬은 O(V^2) 만큼의 메모리가 필요하다 

시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(1)의 시간으로 알아낸다.

 

2) 인접 리스트 (Adjacency List) : 리스트로 연결하여 사용하는 방식

공간복잡도: 간선 개수만큼인 O(E)

시간복잡도: 특정한 노드 X에서 다른 노드 Y로 가는 간선의 비용을 O(V)의 시간으로 알아낸다.

2. 서로소 집합

서로소 집합은 공통 원소가 없는 두 집합이다. 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 이 서로소 집합 자료구조가 바로 union-find 자료구조이다. union연산은 합집합 연산이다. 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어느 것인지 알려준다. 특정한 원소가 속한 집합을 알려주는 기준은 parent node이다. 원소가 속해있는 집합의 parent node가 같으면 두 원소는 같은 집합에 속해있는 것이다. 그리고 원소가 속해있는 집합의 parent node가 다르면 두 원소는 서로소이다 .

3. Union-Find Algorithm

우선 코드는 다음과 같다. 

 

다음과 같은 그래프가 있다 ! 파란색 화살표가 방향성이 있는 간선이다. 이경우 우리는 {1, 2, 3, 4}, {5, 6} 이렇게 두 집합으로 나뉘는구나!를 바로 알수 있다. 

But.. 컴퓨터는 한눈에 알지 못하니까 우리는 union-find알고리즘으로 알려줘야 한다 union-find 자료구조는 tree 자료구조를 이용하여 집합을 표현한다.

1) A, B의 루트 노드 a, b를 각각 찾는다 - 이 그림의 경우 6과 3이 있다면 6의 루트 노드는 5, 3의 루트 노드는 (3 -> 2-> 1) 1이 될 것이다.

2) a를 b의 루트노드로 설정한다. 즉 b가 a를 가리키게 한다 그러면 합집합 완성

이 경우, 보통 번호가 작은 원소가 부모노드가 되도록 구현하는 경우가 많다.

 

 

먼저 parent list를 초기화 해줍니당 이때 각자 자기자신의 부모(root)가 자기자신인걸로 초기화를 해줍니다. 

노드 번호	1	2	3	4	5	6
부모	1	2	3	4	5	6

 

첫번째 union연산은 1과 4를 union연산 하는 것입니다 !! 1과 4를 한 집합으로 합칩시다. 이때 현재 노드 1과 노드 4의 루트 노드는 각각 1, 4인데, 위에서 언급했듯이 일반적으로 더 작은 노드가 더 상위 노드가 되도록, 4의 루트 노드를 1이라고 설정합시다

표에서 4의 부모를 1로 갱신했습니다!

노드 번호	1	2	3	4	5	6
부모	1	2	3	1	5	6

 

다음은 2와 3의 union입니다. 위와 같은 방식으로, 노드 2, 노드 3의 부모노드는 각각 자기자신인 2와 3인 상태입니다. 3이 더 크니까 3이 2를 가리키도록 루트 노드 3의 부모를 2로 설정합니다 

노드 번호	1	2	3	4	5	6
부모	1	2	2	1	5	6

 

다음은 2와 4의 union연산입니다.

노드 2와 노드 4의 부모 노드를 찾으면 노드 2의 루트 노드는 2이고 노드 4의 루트 노드는 1인 상태입니다.  루트 노드끼리 비교해볼까요 ? 루트 노드 2가 1보다 크니까 더 큰 번호인 2의 부모를 1로 설정합니다.

 

노드 번호	1	2	3	4	5	6
부모	1	1	2	1	5	6

 

마지막으로 5와 6의 union연산을 확인해봅시다. 노드 5와 노드 6의 루트 노드는 각각 5, 6이고 5 < 6이니까 6-> 5 로 더 큰 번호인 루트노드 6의 부모를 5로 설정합니다. 그럼 이상으로 union연산을 완료했습니다 !!

특정 원소가 속한 집합을 찾으려면 루트노드를 확인하면 됩니다 예를 들어서 위의 예시에서는 4가 속한 집합은 루트노드가 1인 파란 선들의 집합이고, 6이 속한 집합은 루트노드가 5인 핑크색 집합이 되겠습니다. 

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    if parent[x] != x: # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

 

 

 

그리고 union 연산을 수행하는 함수부분은 다음과 같습니다.

# 두 원소가 속한 집합을 합치기
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

위의 설명과 같이 루트노드를 각각 찾아서 크기를 비교한 다음, parent[i]의 크기가 더 작은 쪽으로 붙여서 두 집합을 합집합으로 만들게 되는 것이지요 !!

 

* 관련문제 사실 이문제를 풀면서 union-find가 문제에서 이렇게 적용되는구나 싶어서 정리하게 되었다 풀이는 다음 포스팅에 !!

https://www.acmicpc.net/problem/10775

10775번: 공항