[알고리즘] 그래프 이론/ 서로소 집합/ 서로소 집합 자료구조/

들어가기 전

 

DFS/BFS와 최단경로는 모두 그래프 알고리즘의 한 유형으로 볼 수 있다.

 

그래프란?

노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조이다.

알고리즘 문제를 접했을 때 서로 다른 개체가 연결되어 있다는 말이 있으면 가장 먼저 그래프 알고리즘을 떠올려야한다. 예를 들어 '여러 개의 도시가 연결되어 있다'와 같은 내용이 등장하면 그래프 알고리즘을 의심해보자.

 

2021.05.27 - [자료구조 알고리즘] - [자료구조] 그래프 (Graph)

[자료구조] 그래프 (Graph)

 

그래프 자료구조 중에서 트리(Tree) 자료구조는 꼭 기억해야 한다.

우선순위 큐를 구현하기 위해서는 최소 힙이나 최대 힙을 이용할 수 있다. 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다. 

 

그래프 VS 트리

	그래프	트리
방향성	방향 그래프 혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

 

그래프 구현 방법

1. 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식
2. 인접 리스트(Adjacency List) : 리스트를 사용하는 방식

다익스트라 최단 경로 알고리즘은 인접 리스트를 이용하는 방식이고, 플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식이다.

 

---

서로소 집합 ( Disjoint Sets)

수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.

 

예

집합 {1, 2, 3}과 집합 {4, 5, 6}은 서로 서로소 관계이다.

집합 {1, 2, 3}과 집합 {3, 4, 5}는 서로 서로소 관계가 아니다. 3이라는 원소가 두 집합에 공통으로 포함되어 있기 때문이다.

 

 

서로소 집합 자료구조

서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조를 말한다.

서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할 수 있다.

• union(합집합) : 2개의 원소가 포함된 각 집합을 하나의 집합으로 합치는 연산
• find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

서로소 집합 자료구조는 union-find(합치기 찾기) 자료구조라고 불리기도 한다.

 

알고리즘

서로소 집합 자료구조는 트리 자료구조를 이용하여 구현한다.

 

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.

        1-1. A와 B의 루트 노드 A', B'를 각각 찾는다.

        1-2. A'를 B'의 부모 노드로 설정한다. (혹은 반대로)

2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.

 

 

예제

{1, 2, 3, 4, 5, 6}



union 1, 4

union 2, 3

union 2, 4

union 5, 6

 

union연산을 하나씩 확인하면서 서로 다른 두 원소에 대해 합집합을 수행해야 할 때는, 각각 루트 노드를 찾아서 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 하면 된다. (작은 루트가 부모 노드가 되고 큰 루트가 자식노드가 된다.)

 

step 0 (초기단계)

 

노드의 개수(V) 크기의 부모 테이블을 초기화한다. 이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다.

현재 원소의 개수가 6이므로, 초기 단계에서는 총 6개의 트리가 존재한다. 

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

 

 

step 1 (union 1, 4)

union 1, 4는 1과 4를 합치는 연산이다.

노드 1과 노드 4의 루트 노드를 각각 찾아 보면 1과 4이기 때문에 더 큰 번호에 해당하는 루트 노드 4를 자식노드로 설정하고, 더 작은 번호에 해당하는 루트 노드 1을 부모노드로 설정한다.

 

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

 

 

step 2 (union 2, 3)

union 2, 3은 2와 3을 합치는 연산이다.

노드 2과 노드 3의 루트 노드를 각각 찾아 보면 2과 3이기 때문에 더 큰 번호에 해당하는 루트 노드 3을 자식노드로 설정하고, 더 작은 번호에 해당하는 루트 노드 2를 부모노드로 설정한다.

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

 

 

step 3 (union 2, 4)

노드 2과 노드 4의 루트 노드를 각각 찾아 보면 2과 1이기 때문에 더 큰 번호에 해당하는 루트 노드 2를 자식노드로 설정하고, 더 작은 번호에 해당하는 루트 노드 1을 부모노드로 설정한다.

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

 

 

step 4 (union 5, 6)

노드 5과 노드 6의 루트 노드를 각각 찾아 보면 5과 6이기 때문에 더 큰 번호에 해당하는 루트 노드 6을 자식노드로 설정하고, 더 작은 번호에 해당하는 루트 노드 5를 부모노드로 설정한다.

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

이상으로 모든 union 연산을 처리했다.

 

이 알고리즘에서 유의할 점은 union 연산을 효과적으로 수행하기 위해 부모 테이블을 항상 가지고 있어야 한다는 점이다. 또한, 루트 노드를 즉시 계산할 수 없고, 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다.

 

예를 들어 위의 step 4 그림에서 노드 3의 부모 노드는 2라고 설정되어 있다. 다만, 노드 2의 부모 노드는 1이기 때문에 최종적으로 노드 3의 루트 노드는 1이라고 볼 수 있다.

---

 

소스코드

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


# 노드의 개수와 간선(union 연산)의 개수 입력받기
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('각 원소가 속한 집합의 루트 노드: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

입력

6 4 # v e 
1 4 
2 3
2 4
5 6

출력

각 원소가 속한 집합의 루트 노드: 1 1 1 1 5 5 
부모 테이블: 1 1 2 1 5 5

 

결과를 보면 루트 노드가 같은 1, 2, 3, 4가 같은 집합이고 5, 6이 같은 집합임을 알 수 있다. {1, 2, 3, 4}, {5, 6}

 

또한, 노드 3의 부모 노드는 2라고 설정되어 있다. 다만, 노드 2의 부모 노드는 1이기 때문에 최종적으로 노드 3의 루트 노드도 1이라고 볼 수 있다.

 

 

---

경로 압축 (Path Compression)

find 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신하는 기법이다.

 

 

개선된 서로소 집합 알고리즘 코드

# 특정 원소가 속한 집합을 찾기
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


# 노드의 개수와 간선(union 연산)의 개수 입력받기
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('각 원소가 속한 집합의 루트 노드: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

입력

6 4
1 4
2 3
2 4
5 6

출력

각 원소가 속한 집합의 루트 노드: 1 1 1 1 5 5 
부모 테이블: 1 1 1 1 5 5

 

개선된 알고리즘을 사용하면 경로 압축을 통해 부모 테이블에 루트 노드가 담기게 된다.

 

 

 

출처

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년