[알고리즘] 서로소 집합 알고리즘

[정의]

• union 과 find 연산으로 이루어진다. ( union-find 자료구조 라고도 불린다. )
• 코드를 보면 알겠지만, 집합은 같은 부모 노드를 가지고 있다는것으로 묶을 수 있고, 따라서 union  함수는 부모 노드를 합치는 함수라고 할 수 있다. find 함수는 부모 노드를 찾는 함수이다.
  find를 하여서 부모노드를 찾았는데 서로 다르면 다른 집합이고, 서로 같으면 같은 집합이다.
• find를 통해 부모 노드를 찾을 때는, 재귀적으로 부모를 거슬러 올라가 자기 자신을 부모 노드로 갖는 노드를 찾는다. 왜냐면 자기 자신을 부모 노드로 갖는 노드가 루트 노드가 되기 위한 정의이기 때문이다.
• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 한다.
• 무방향 그래프에서 적용 가능하다. 그래프를 번호가 더 작은 값( 임의로 정한 규칙이다.)을 루트로 갖는 트리처럼 다루기 때문.

(1, 2) 와 (3, 4) 는 서로소 관계 이다.

 

(1,2) 와 (2,3) 은 서로소 관계가 아니다.

 

 

 

[기본적인 서로소 집합 알고리즘]

 

1. union 연산

• 1 union 4

각 노드는 현재 자기 자신을 부모 노드로 가지고 있다. ( 초기화 상태 )

1 union 4 연산을 수행하면, 1의 부모 노드와 4의 부모 노드를 비교해서 더 작은 값인 1이 1과 4의 부모노드가 된다.

 

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

 

• 2 union 3
• 2 union 1

2 union 3 연산을 하면 위의 연산에서와 마찬가지로 두 노드의 부모노드는 2가 된다.

2 union 1 을 하면, 1 과 2의 부모 노드는 1이 될 것이다.

 

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

 

• 5 union 6

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

 

# a union b
def union_parent(parent_list,a,b):
    a = find_parent(parent_list,a)
    b = find_parent(parent_list,b)
    if a<b:
        parent_list[b] = a
    else:
        parent_list[a] = b

a 와 b의 부모 노드를 각각 찾아서, 더 작은 값을 부모 노드로 대체한다. 

 

# union 연산 하는 과정
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent_list, a, b)

 

2. find 연산

# 부모 찾는 함수
def find_parent(parent_list, X):
    if parent_list[X] != X:
        return find_parent(parent_list, parent_list[X])       # 부모노드가 자신인게 곧 루트노드
    return X

재귀적으로 부모노드를 거슬러 올라가 루트 노드를 찾는다.

말 장난 같지만, 결국 X의 루트 노드를 찾는 함수이다.

 

3. 전체 코드

# 부모 찾는 함수
def find_parent(parent_list, X):
    if parent_list[X] != X:
        return find_parent(parent_list, parent_list[X])       # 부모노드가 자신인게 곧 루트노드
    return X

# union
def union_parent(parent_list,a,b):
    a = find_parent(parent_list,a)
    b = find_parent(parent_list,b)
    if a<b:
        parent_list[b] = a
    else:
        parent_list[a] = b

v, e = map(int, input().split())

# 자기 자신을 부모로 갖겠끔 해서 초기화
parent_list = [i for i in range(v+1)] 

# union 연산
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent_list, a, b)

# 각 원소의 부모 노드 출력
for i in range(1, v+1):
    print(find_parent(parent_list,i), end=' ')
print()

# 부모테이블 어떻게 생겼는지 출력
for i in range(1, v+1):
    print(parent_list[i], end= ' ')

---

[개선된 서로소 집합 알고리즘] 

1. 경로 압축 기법 소스코드

find_parent 함수를 보면 재귀 함수임을 알 수 있는데, 매번 모든 노드의 루트 노드를 재귀로 찾아가는게 비효율적이라 생각될 수 있다. 따라서 DP 테이블에 저장하듯, 처음부터 부모 테이블에 루트 노드의 값을 저장하여 굳이 재귀적으로 매번 검색하지 않아도 되겠끔 만들 수 있다.

 

def find_parent(parent_list, X):
	if X != parent_list[X]:
		parent_list = find_parent(parent_list, parent_list[X])
	return parent_list[X]

find_parent 함수 부분을 다음 코드로 수정해주면 된다.

 

2. 이외

위의 경로 압축 기법 외에도 많지만, 실제  코테에서 경로 압축이면 충분하다고 한다.

 

---

[시간 복잡도]

• 노드가 V이고, 따라서 최대 V-1 의 union 연산과 M개의 find 연산이 가능할 때, 
  \( O(V + M(1+ ln_{2-M/V}V) \)  가 걸린다.
• 예를 들어 노드의 개수가 1000개고, union 및 find 연산이 총 100만번 시행 된다면, 약 1,000만 번 가량의 연산이 필요하다고 이해하면 된다.

---

[서로소 집합 이용한 무방향 그래프의 사이클 판별] 

 

① 과② union 과정이 끝나고 나면, 노드 1, 2, 3의 부모(root) 노드는 1이 된다.

③ union 과정을 수행하기 전, 노드 1과 3의 부모 노드를 확인 했는데 이미 같은 집합에 속한다면,

사이클 관계에 있다는걸 알 수 있다.

 

아래는 관련 코드이다.

 

# find
def find_parent(parent_list, X):
    if X != parent_list[X]:
        parent_list[X] = find_parent(parent_list,parent_list[X])
    return parent_list[X]

# union
def union_parent(parent_list, a, b):
    a = find_parent(parent_list,a)
    b = find_parent(parent_list,b)
    if a < b :
        parent_list[b] = a
    else:
        parent_list[a] = b

# 노드 간선 입력 및 부모테이블 초기화
v, e = map(int, input().split())
parent_list = [i for i in range(v+1)]

# 사이클 발생 여부
cycle = False
# 문제에서 주어진 그래프대로 union
for i in range(e):
    a, b = map(int, input().split())

    # 사이클이 발생했다면 합집합 수행 종료
    if find_parent(parent_list,a) == find_parent(parent_list,b):
        cycle = True
        break
    else:
        union_parent(parent_list, a, b)

 

 

참고한 책 ; 나동빈 (2020). <이것이 취업을 위한 코딩 테스트다 with 파이썬>. 서울시: 한빛미디어.