[알고리즘] union find 연산 2

1. 서로소 집합 - Union/Find 연산

공통원소가 존재하지 않는 집합, 그러한 관계를 의미한다.

이 서로소 집합에 대해 Union(개별적인 두 노드(원소)에 대해 동일한 부모노드를 설정하여 하나의 집합(합집합)으로 합치는 과정)연산을 거치면 동일한 하나의 집합으로 만들 수 있다.

이 후 Find 연산으로, 각 원소들의 부모노드를 확인하여 부모노드가 같을 경우 같은 집합으로 취급하여 합집합인지 서로소집합인지 판별한다.

1-1. 연산과정

Union(1,4), Union(2,3), Union(2,4), Union(5,6)의 연산으로 합집합을 구성한다고 해보자.

• step 1

최초 과정은 노드 개수만큼 배열 및 부모테이블을 구성하는 것이며, 이때 처음 상태의 부모테이블은 각각 자기 자신이 된다(자기자신 = 부모노드).

• step 2

노드1과 노드4를 합쳐 합집합으로 만드는 과정을 진행한다.

부모노드는 두 노드 중 숫자가 작은 노드로 설정되며, Union 연산이후엔 두 노드는 더이상 서로소 집합이 아니다.

• step 3

마찬가지로 노드2와 노드3에 대한 합집합 연산을 수행한다.

• step 4

노드2와 노드4에 대해 합집합 연산을 수행해보자.

• 각 노드에 대해 부모노드를 파악한다.
• 노드2의 부모노드는 2이고, 노드4의 부모노드는 1인 상태에서 두 노드를 합칠때는 같은 부모노드로 만드는 연산임을 유의하자.
• 이때 부모노드는 작은 숫자를 기준으로 설정하므로, 더 큰 부모노드를 가지는 노드2에 대해 부모노드를 1로 설정한다.
• 결과적으로 노드2의 부모노드는 노드1이 되었고, 이에 따라 1,2,4는 같은 집합에 속하는 원소가 되었다.

• step 5

결과적으로 각 노드(원소)들을 하나의 집합으로 구성할 수 있고, find 연산을 통해 두 노드의 연결관계를 정의할 수 있다.

1-2. 재귀적인 과정을 통해 루트노드 탐색 가능

합집합 관계에 있는 노드들에 대해서, 루트 노드가 단계별(계단과 같이)로 구성되어 있는 경우엔 바로 접근해서 알 수는 없고 재귀적으로(순차적으로) 루트 노드를 파악하여 최종적인 부모노드를 파악할 수 있다.

즉 위와 같이 노드3의 부모노드를 확인하기 위해선, 노드3 > 노드2 > 노드1의 순으로 단계적으로(재귀적으로) 부모노드를 파악해야 알 수 있다(거슬러 올라가야 한다).

1-3. 알고리즘 구현 - 기본 형태(재귀적 호출)

노드 개수 v와 간선 개수 e를 입력받은 후, 각 노드의 루트노드를 구성하고(같은 집합으로 합치고) 이를 탐색하는(find) 알고리즘을 구현해 본다.

    #특정 노드에 대한 루트노드 찾기
    def findParent(parent, x):
        if parent[x] != x: #자기 자신이 아니라면, 해당 루트 노드의 루트노드를 찾는다.
            return findParent(parent, parent[x])
            #parent[x], 즉 해당 루트노드의 루트노드를 찾는다.
            #parent는 부모테이블
        return x

    #union 연산
    def unionParent(parent, a, b):
        a = findParent(parent, a)
        b = findParent(parent, b)
        if a < b: #a의 루트노드가 최종적인 루트노드가 되도록 노드 b를 설정
            parent[b] = a
        else :
            parent[a] = b

    #입력
    #노드개수와 간선개수
    import sys
    v, e = map(int, sys.stdin.readline().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, sys.stdin.readline().split())
        unionParent(a, b) #a와 b를 합치는 과정

    #각 원소의 소속집합(루트노드)
    for i in range(1, v+1):
        print(findParent(parent, i), end=' ')
    print()
    #부모테이블 내용
    ##부모테이블과 각자 속한 루트노드는 다른 내용일 수 있다(실제 루트노드는 거쳐거쳐 확인하므로)
    for i in range(1, v+1):
        print(parent[i], end=' ')

1-4. 알고리즘 구현 - 개선된 union find 연산

위 방법과 같이 재귀적으로 union find 호출 시, 거쳐거쳐서 루트노드를 확인한다는 점에서 단계가 늘어날 수록 그만큼 find연산이 늘어나고 비효율적일 수 있다.

위와 같이 단계구성이 많아진다면, 최악의 경우 노드개수만큼 시간복잡도가 늘어난다(O(V)).
따라서 개선된 형태인 경로압축(path compression)을 활용하는데, 이때 찾기함수를 호출하였을 때 부모값을 바로 갱신한다.

def findParent(parent, x):
    if parent[x] != x: #자기 자신이 아니라면, 해당 루트 노드의 루트노드를 찾는다.
        return findParent(parent, parent[x])
        #parent[x], 즉 해당 루트노드의 루트노드를 찾는다.
        #parent는 부모테이블
    return x

즉 위의 재귀적으로 탐색하는 부분을 아래와 같이 그때그때 찾을때마다 부모노드를 갱신하는 형태로 바꾼다.

마치 Topdown 하듯이 각 단계마다 부모노드 값을 저장한다.

def findParent(parent, x):
    if parent[x] != x: #자기 자신이 아니라면, 해당 루트 노드의 루트노드를 찾는다.
        parent[x] = findParent(parent, parent[x]) #재귀호출이 아니라, TOpDown 방식으로 값을 저장한다.
    return parent[x]

1-5. union find 연산을 활용한 cycle 탐색

graph 내부에서 cycle, 즉 두 노드에 대해 양방향 탐색이 가능한 경로가 존재하는지 판별하는 도구로 union find 연산을 사용할 수 있다.

다만 무향 graph에서 union find연산을 활용하고, 방향 graph에서는 DFS를 이용하여 cycle을 확인할 수 있다.

위와 같은 graph가 있을때 union find 연산을 이용해서 cycle을 어떻게 판별할 수 있을까?

일단 기본적으로 cycle은 같은 부모노드를 바라본다라는 시점에서 출발하는데, cycle이 발생하지 않는다면 cycle이 발생하는 알고리즘을 구성할 수 있다.

• step 1

각각의 간선을 확인해가면서 각 노드의 루트노드를 확인한다.

간선 1,2의 노드들의 루트노드가 최초 1,2인 상태에서 → 더 작은 루트노드인 1을 기준으로 union연산을 진행한다.

• step 2

위 과정을 반복 수행한다.

최종적으로 동일한 루트노드를 구성하였으며, cycle이 발생하는 graph를 구성하게 되었다.

이를 알고리즘으로 구성하면 아래와 같다.

#기존 union find를 개선한 형태의 알고리즘
#특정 노드에 대한 루트노드 찾기
def findParent(parent, x):
    if parent[x] != x: #자기 자신이 아니라면, 해당 루트 노드의 루트노드를 찾는다.
        parent[x] = findParent(parent, parent[x]) #재귀호출이 아니라, TOpDown 방식으로 값을 저장한다.
    return parent[x]

#union 연산
def unionParent(parent, a, b):
    a = findParent(parent, a)
    b = findParent(parent, b)
    if a < b: #a의 루트노드가 최종적인 루트노드가 되도록 노드 b를 설정
        parent[b] = a
    else :
        parent[a] = b

#입력
#노드개수와 간선개수
import sys
v, e = map(int, sys.stdin.readline().split())
#부모테이블
parent = [0] * (v+1)
for i in range(1, v+1):
    parent[i] = i

#cycle판별 알고리즘 : cycle이 아닐 경우 union 과정 수행
cycle = False
for i in range(e):
    a, b = map(int, sys.stdin.readline().split())
    if findParent(parent, a) == findParent(parent, b):
        cycle = True #루트노드가 같아서 cycle이 발생하였다면 즉시 반복문 종료
        break
    else:
        unionParent(parent, a, b)
        
if cycle:
    print("사이클이 존재하는 무향 그래프")
else:
    print("사이클이 존재하지 않은 무향 그래프")

2. 참고자료

이코테 2021 - union find
https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8