다익스트라나 플로이드 워셜과 같이 여러 기타 그래프 탐색 알고리즘에 대해서 정리해보고자 한다. 먼저, 서로소 집합이다. 서로소 집합 자료구조는 union-find 자료구조라고 불리기도 한다.

서로소 집합

먼저, 서로소 집합의 수학적인 의미는 공통적인 원소가 없는 두집합을 의미한다. 두 집합 {1,2}와 {3,4}는 서로소 집합이다. 하지만, {1,2},{2,3}은 2라는 공통된 원소를 가지는 집합이다. 서로소 집합 자료구조는 서로소 부분집합들로 나뉜 원소들의 데이터를 처리하기 위한 자료구조이다. union 연산과 find 연산으로 조작 가능하다.

union 연산은 합집합 연산이다. 말 그대로, 2개의 집단을 하나의 집합으로 합치는 연산이다. find 연산은 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 서로소 집합 자료구조를 구현할때는 트리 자료구조를 이용하여 집합을 표현한다.

주어진 데이터에 대한 union 연산 정보가 주어졌을때 아래의 알고리즘으로 서로소 집합을 계산한다.

1. union 연산을 확인하여 서로 연결된 두 노드 A와 B를 확인한다.
   1.1 A와 B의 루트 노드 A'와 B'를 찾는다.
   1.2 A'를 B'의 부모노드로 설정한다. ('B' 가 'A'를 가리키게 한다.)
2. 모든 union 연산을 처리할때까지 1번의 과정을 반복한다.

A와 B 노드 중 더 작은 노드를 부모노드로 지정하는 경우가 많다.

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

로 union 연산을 모두 수행하였다. union 연산을 효율적으로 수행하기 위해서는 항상 부모 테이블이 있어야한다. 그리고, 루트노드를 한번에 계산 못하고 부모 테이블을 거쳐서 거슬러 올라가야한다.

union 연산의 종료와 함께 노드 간의 관계를 한눈에 확인가능하다. 전체 데이터인 원소가 {1,2,3,4}와 {5,6}으로 나누어진다는 것을 알 수 있다. union 연산을 토대로 그래프를 그리면 연결성으로 손쉽게 집합의 형태를 확인할 수 있다.

• python code

def find_parent(parent,x):
    if parent[x]!=x: # 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


v,e=map(int,input().split())
parent=[0]*(v+1) # 부모 테이블을 각 노드 자신의 값으로 초기화
for i in range(1,v+1):
    parent[i]=i

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

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=' ')

코드 실행결과에서 알 수 있듯이, 실제 원소가 속한 집합은 해당 원소의 루트 노드값을 출력하고, 부모 테이블은, 바로 상위에 존재하는 노드를 가리키는 것을 알 수 있다. 이렇게 구현하면 답은 구할 수 있지만, find_parent함수 자체가 비효율적으로 동작하게 된다. 최악의 경우 find 함수가 모든 노드를 다 확인해서 시간 복잡도가 $O(V)$일 수 있다.

한가지 예시를 들어 생각해보자, {1,2,3,4,5} 의 데이터에 union 연산을 차례대로, (4,5) (3,4) (2,3) (1,2) 순으로 한다고 생각해보자. 연산 처리가 완료되면 아래처럼 일렬로 나열하는 형태가 된다.

최악의 경우를 생각했을때, 노드 5의 루트를 찾기 위해서 노드 5→4→3→2→1 로 거슬러 올라가서 찾아야한다. 전체 시간 복잡도는 $O(VM)$이 될 수 있다. (여기서 M은 union 연산의 개수) 따라서, find함수를 간단하게 최적화 해주어, 부모 테이블에 루트 노드가 바로 저장되게 할 것이다.

바로 경로 압축기법을 사용하는 것이다. 이전에 반환하던 x를 parent[x]로 반환할 뿐이다.

def find_parent(parent,x):
    if parent[x]!=x: # parent[x]==x 는 루트 노드라는 것을 의미한다.
        parent[x]=find_parent(parent,parent[x])
    return parent[x]

이렇게 수정하게 되면 노드에 대해 find 함수 호출한 후에 해당 노드의 루트 노드가 바로 부모 노드가 된다. 이전과 동일하게 {1,2,3,4,5} 의 데이터에 union 연산을 차례대로, (4,5) (3,4) (2,3) (1,2) 순으로 한다면 모든 부모 테이블이 1값으로 저장될 것이고 그래프로 표현하면 아래의 결과를 가질 것이다.

개선된 서로소 집합 알고리즘은 다음과 같다.

• python code

def find_parent(parent,x):
    if parent[x]!=x: # 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


v,e=map(int,input().split())
parent=[0]*(v+1) # 부모 테이블을 각 노드 자신의 값으로 초기화
for i in range(1,v+1):
    parent[i]=i

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

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=' ')

실행결과는 다음과 같다.

경로압축 방법을 적용한 서로소 집합 알고리즘의 시간 복잡도는 $O(V+M(1+log_{2- \frac M V} V))$ 이다. 노드의 개수가 1,000개 이고 union 및 find 연산이 100만번 수행된다면 $V+Mlog_2V$를 계산해서 약 1,000만 번 가량의 연산이 필요하다.

서로소 집합을 활용한 사이클 판별

서로소 집합은 무방향 그래프에서 사이클을 판별할때 사용할 수 있다. 앞서 union 연산은 그래프에서의 간선으로 표현 가능했었다. 간선을 하나씩 확인하면서 두 노드가 포함된 집합을 합치는 과정을 반복하는 것으로 사이클을 판별할 수 있다.

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
   1.1 루트 노드가 다르면 union 연산을 수행한다.
   1.2 루트 노드가 같다면 cycle이 발생한 것이다.
2. 그래프에 포함되어있는 모든 간선에 1번을 실행한다.

그래프의 cycle 판별 과정을 살펴보자

사이클 판별 알고리즘은 그래프에 포함되어 있는 간선의 개수가 E개일 때 모든 간선을 하나씩 확인하여 매 간선마다 union 및 find 함수를 호출해서 동작한다.

def find_parent(parent,x):
    if parent[x]!=x: # 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


v,e=map(int,input().split())
parent=[0]*(v+1) # 부모 테이블을 각 노드 자신의 값으로 초기화
for i in range(1,v+1):
    parent[i]=i

cycle=False

for i in range(e):
    a,b=map(int,input().split())
    if find_parent(parent,a)==find_parent(parent,b):
        cycle=True
        break
    else:
        union_parent(parent,a,b) # union 연산 수행

if cycle:
    print("cycle 발생")
else:
    print("cycle 발생하지않음")

이전의 서로소 집합 알고리즘에서 cycle 여부만 판단할 수 있게 간선의 수만큼 실행하게끔 코드를 작성하면된다.

Reference

이것이 취업을 위한 코딩테스트다 with 파이썬