그래프 이론 - 서로소집합(disjoint set) 기본개념1 -

1. 그래프 기본 개념 간단히 복습

 

크루스칼 알고리즘 >>> 그리디 알고리즘

 

위상 정렬 알고리즘 >>> 큐, 스택자료구조를 이용

 

----------------------------------------------------------------

 

그래프(graph)란 노드(node)와 노드 사이 연결된 간선(edge)의 정보를 가지고 있는 자료구조

 

알고리즘 문제를 풀 때, "서로 다른 개체(객체)가 연결되어있다"라고 한다면 그래프 알고리즘을 가장 먼저 떠올려야한다.

 

예를 들어 "여러개의 도시가 연결되어 있다"라고 한다면 그래프 알고리즘을 의심할 필요가 있다

 

-----------------------------------------------------------------

 

그래프 자료구조 중 트리 자료구조는 다양한 알고리즘에서 사용되므로 반드시 기억해야한다.

 

다익스트라 최단 경로 알고리즘에는 우선순위 큐가 사용되는데, 우선순위 큐를 구현하기 위해 최소 힙(min heap)이나 최대 힙(max heap)을 이용할 수 있다

 

최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다.

 

트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속한다.

 

트리는 전통적인 수학에서는 무방향 그래프로 간주하나, 컴퓨터 공학에서는 보통 방향 그래프라고 생각한다.

 

그래프와 트리를 비교하면

 

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

 

그래프를 구현하는 방법으로 인접행렬(2차원 배열을 사용), 인접 리스트(리스트 사용) 방식이 있다.

 

노드의 개수 V, 간선의 개수 E에 대하여 인접 행렬을 이용하는 방식은 간선 정보를 저장하기 위해 $O(V^{2})$만큼의 메모리 공간이 필요하다.

 

반면 인접 리스트를 이용할 때는 간선의 개수인 $O(E)$만큼의 메모리 공간이 필요하다.

 

인접 행렬은 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있다.

 

반면 인접 리스트는 O(V)만큼의 시간이 소요된다.

 

---------------------------------------------------------------

 

다익스트라 알고리즘은 인접 리스트를 이용하는 방식으로 노드의 개수가 V개일때, V개의 리스트를 만들어서 각 노드와 연결된 모든 간선에 대한 정보를 리스트에 저장했다.

 

플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식이다. 

 

모든 노드에 대하여 다른 노드로 가는 최소 비용을 $V^{2}$크기의 2차원 리스트에 저장한 뒤에 해당 비용을 갱신해서 최단 거리를 계산했다.

 

최단 경로를 찾는 문제에서 노드의 개수가 적다면 플로이드 워셜 알고리즘을 이용할 수 있지만,

 

노드와 간선의 개수가 많다면 우선순위 큐를 이용한 다익스트라 알고리즘을 이용하면 유리하다.

 

 

2. 서로소 집합

 

수학에서 서로소 집합(disjoint set)이란 공통 원소가 없는 두 집합이다. 

 

서로 중복 포함된 원소가 없는 집합들을 말한다.

 

집합 {1,2}와 {3,4}는 서로소 관계이다.

 

반면 집합 {1,2}와 {2,3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있어서 서로소 관계가 아니다.

 

 

3. 서로소 집합 자료구조

 

집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이러한 "하나의 특정 멤버"를 대표자(representative)라고 한다.

 

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

 

서로소 집합 자료구조는 union, find 2개의 연산으로 조작한다. 그래서 union-find 자료구조라고도 불린다.

 

두 집합이 서로소 관계인지를 확인할 수 있다는 말은, 각 집합이 어떤 원소를 공통적으로 가지고 있는지를 확인할 수 있다는 말이다.

 

union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

 

find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

 

 

4. 서로소 집합 자료구조의 표현

 

트리 자료구조를 이용해 표현할 수 있다.

 

자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 된다

 

 

초기에 v개의 정점이 존재할때, 자기 자신이 부모가 되도록, 즉 자기 자신을 가리키도록 설정한다.

 

현재 정점이 인덱스 i일때, 리스트의 원소 tree[i]는 i의 부모 노드를 저장한다.

 

초기에는 6개의 트리가 위와 같이 존재하고 있다.

 

리스트 안에는 오직 정점의 부모만을 가지고 있다.

 

하지만 실제로 union 연산 후에 루트를 확인하고자 할때는 재귀적으로 부모를 거슬러 올라가 확인을 한다

 

 

5. 예시를 통해 이해하는 union 알고리즘

 

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

 

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

 

1-2) A'을 B'의 부모 노드로 설정(B'이 A'을 가리키도록 함)

 

2) 모든 union 연산을 처리할 때까지 1)번 과정을 반복--------------------------------------------------------------------------------------------------

 

전체집합 {1,2,3,4,5,6}의 6개 원소로 구성되어 있는 상황을 생각하자.

 

union(1,4), union(2,3), union(2,4), union(5,6)의 4가지 연산이 주어져있다고 생각해보자.

 

이 4개의 union 연산은 각각 "1과 4는 같은 집합", "2와 3은 같은 집합", "2와 4는 같은 집합", "5와 6은 같은 집합"이라는 의미를 가진다.

 

이때 4개의 union연산이 수행된 후에 전체 원소들이 어떠한 형태의 부분집합으로 나뉘어질까?

 

union 연산은 그래프 형태로 표현될 수 있다. 

 

각 원소는 그래프에서의 노드로 표현되고 "같은 집합에 속한다"는 정보를 담은 union 연산들은 서로 연결해야 하니까 간선으로 표현된다.

 

즉 6개의 노드가 있고 4개의 간선이 존재하는 그래프로 바꾸어 생각할 수 있다.

 

union 연산을 모두 수행하고 나서 관계를 시각화하면 다음과 같다

 

일반적으로 서로소 집합을 그림으로 표현할 때는 번호가 큰 노드가 번호가 작은 노드를 간선으로 가리키도록 트리 구조를 이용해 그림을 그리게 된다.

 

트리 구조상 번호가 작은 노드가 부모가 되고, 번호가 큰 노드가 자식이 된다.

 

위 그림을 보자마자 노드 간의 관계를 빠르게 확인할 수 있다.

 

전체 원소가 {1,2,3,4}와 {5,6}이라는 두 집합으로 나누어지는 것을 알 수 있다.

 

노드 1,2,3,4가 같은 집합에 속하며, 노드 5,6이 같은 집합에 속한다.

 

이렇게 union 연산을 토대로 그래프를 그리면 연결성으로 손쉽게 집합의 형태를 확인할 수 있다

 

특히 노드 3에서 노드 1로 간접적으로 노드 2를 거쳐서 이동할 수 있으므로, 노드 3과 노드 1은 같은 집합에 있는 것으로 이해할 수 있다.

 

반면 노드 1과 노드 5는 서로 이어져 있지 않아 다른 집합에 속한다고 생각할 수 있다.

 

 

6. 그림을 통해 이해하는 union 알고리즘

 

union 연산을 하나씩 확인하면서 서로 다른 두 원소에 대해 union을 수행하려면

 

각각 루트 노드를 찾아서 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 만들면 된다.

 

위의 상황에서 union(1,4) 연산을 수행한다면? 1과 4를 합친다.

 

이때는 노드 1과 노드 4의 루트 노드를 각각 찾는다 

 

현재 루트 노드는 각각 1과 4이고 더 큰 번호에 해당하는 4의 부모를 1로 설정하자.

 

일반적으로 union 연산을 구현할때, 더 번호가 작은 원소가 부모 노드가 되도록 구현하는 경우가 많다

 

노드 4의 부모를 1로 설정한다는 말은 노드 4와 노드 1을 간선으로 연결하는 그래프 형태로 표현할 수 있다

 

 

union(2,3)을 수행한다면? 2와 3을 합치고, 2의 번호가 더 적으므로 3의 부모를 2로 설정한다

 

여기에 union(2,4)를 수행한다면? 2와 4를 합칠 것이다.

 

2의 루트 노드는 2이고, 4의 루트노드는 1이다.

 

루트 노드의 번호가 더 큰 2의 부모를 1로 설정한다

 

 

루트 노드랑 부모 노드는 다르네

 

3의 부모 노드는 2이지만, 현재 루트 노드는 1이거든

 

리스트에 부모 노드를 저장

 

마지막으로 union(5,6)을 한다면? 5와 6의 루트 노드를 찾는다.

 

각각 5와 6이고, 더 큰 번호인 6의 부모를 5로 설정

 

조금 더 직관적으로 그려보자면? 초기 상태에서 union(1,4)를 수행하면

 

 

여기에 union(2,3)을 수행하면..

 

 

union(2,4)를 하면 어떻게 될까..?

 

{1,4}랑 {2,3}을 합칠거고, 가장 작은 번호를 부모 노드로 가리키도록 만든다

 

{2,3}의 루트인 2번이 {1,4]의 루트인 1번을 가리키도록 만들자

 

 

그리고 union(5,6)을 수행하면, 6번이 5번을 가리키도록 5,6을 합치면 된다.

 

위 과정을 보면 union 연산을 효과적으로 수행하려면 부모를 저장한 리스트를 계속해서 가지고 가야한다.

 

그리고 집합의 루트 노드를 즉시 계산할 수는 없고 부모 노드를 저장한 리스트를 거슬러 올라가야한다.

 

 

위 그림에서 노드 3의 루트 노드를 찾고 싶다. 그러면 노드 3의 부모 노드 2번으로 이동하고, 다음 노드 2의 부모 노드인 1번으로 이동해야한다.

 

1번 노드를 확인할 때, 부모 노드가 자기 자신과 동일하므로, 노드 1이 최종 루트 노드임을 알 수 있다.

 

서로소 집합 알고리즘으로 루트 노드를 찾고 싶다면 재귀적으로 부모를 거슬러 올라가 부모 노드와 자기 자신 번호가 동일할 때까지 확인해야한다.

 

 

7. 기본 서로소 집합 알고리즘 구현

 

위의 알고리즘을 소스코드로 구현해보자.

 

기본적으로 집합의 대표자인 루트 노드를 찾는 find 함수와 두 원소가 속한 집합을 합치는 union 함수가 필요하다.

 

find함수는 부모 번호를 저장하고 있는 리스트(parent)에서 재귀적으로 혹은 반복적으로 거슬러 올라가,

 

현재 노드 번호가 저장된 값과 동일할 때까지 반복하면 그것이 루트 노드(대표자)가 된다

 

반복문이 더 빠르다고 알려져있다

 

##특정한 원소 x가 속한 집합을 찾는다
##x가 속한 집합의 대표자를 찾는 함수
##재귀적 구현

def find_parent(parent,x):
    
    ##루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출

    if parent[x] != x:
        
        return find_parent(parent,parent[x])
    
    return x

##반복문 구현

def find_parent(parent,x):
    
    ##루트노드가 아니라면, 루트 노드를 찾을 때까지 반복적으로 거슬러 올라감
    while x != parent[x]:
        
        x = parent[x]
    
    return x

 

union(a,b)함수는 a의 대표자를 찾고, b의 대표자를 찾은 다음에 (문제 조건에 따라 다르겠지만 일반적으로)

 

루트 노드의 번호가 큰 경우를 작은 경우에 가리키도록 만든다(작은 경우가 부모가 되도록)

 

##두 원소가 속한 집합을 합치는 union 함수

def union_parent(parent,a,b):
    
    a = find_parent(parent,a) ##a의 대표자를 찾고
    b = find_parent(parent,b) ##b의 대표자를 찾고

    if a < b: ##b의 루트노드가 더 크다면,
        
        parent[b] = a ## 더 큰 노드 b의 부모를 더 작은 노드인 a로 설정

    else:  ##a의 루트 노드가 더 크다면
        
        parent[a] = b ## 더 큰 노드 a의 부모를 더 작은 노드인 b로 설정

 

 

계속 이야기하지만, 문제에서 더 작은 노드의 부모를 더 큰 노드로 하라면, 당연히 설정을 바꿔야한다.

 

그렇지만 기본은

 

a의 대표자를 찾고

b의 대표자를 찾고

 

a(혹은 b)의 부모를 b(혹은 a)로 대체한다는 점이다.

 

입력을 받고 실제로 수행해보자.

 

##특정 원소가 속한 집합을 찾는다

def find_parent(parent,x):
    
    ##루트 노드가 아니라면, 루트 노드를 찾을 때까지 반복적으로 호출함

    while x != parent[x]:
        
        x = parent[x]
    
    return x


##두 원소가 속한 집합을 합친다.

def union_parent(parent,a,b):
    
    a = find_parent(parent,a) ##a의 대표자를 찾고

    b = find_parent(parent,b)  ##b의 대표자를 찾고

    if a < b:  ##b가 더 크다면
        
        parent[b] = a ##b의 부모를 더 작은 a로 설정
    
    else: ##a가 더 크다면
        
        parent[a] = b



##노드의 개수와 간선의 개수

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 2 1 5 5 
"""

 

union, find 함수를 정의하고, 입력 노드, 간선을 받고나서 부모 테이블을 자기 자신으로 먼저 초기화한다.

 

union 연산 정보를 입력받아 전부 수행한 뒤에 각 노드 1,2,3,4,5,6의 대표자를 출력하니 그림에서 확인한것처럼

 

1,1,1,1,5,5라는 것을 알 수 있다

 

각 노드의 루트 노드가 1,1,1,1,5,5라는 뜻이다.

 

루트 노드가 동일한 원소끼리 동일한 집합을 이룬다.

 

그렇다면 우리는 각 노드가 {1,2,3,4}와 {5,5}의 두 집합으로 나뉜다는 것을 알 수 있다.