[알고리즘] Union-Find(유니온 파인드)로 무방향 그래프에서 사이클(cycle) 찾기

1️⃣ 유니온 파인드란?

Union-Find는 서로소 집합을 찾는 알고리즘으로, 서로소 집합은 공통 원소가 없는 두 집합을 의미한다.

 

아래와 같이 루트 노드를 찾고(find), 연결된 두 노드를 합치는(union) 연산으로 이루어져 있다.

def find(parent, x): # 부모 찾기
    if parent[x] != x:
        parent[x] = find(parent, parent[x]) # 루트 노드가 아닌 경우, 재귀호출을 통해 루트 노드를 찾음
    return parent[x]

def union(parent, x, y): # 합치기
    x = find(parent, x)
    y = find(parent, y)
    
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

 

2️⃣ 유니온 파인드로 사이클을 찾으려면?

아래와 같은 순서로 코드를 실행하면 된다.

 

모든 간선에 대해 아래 과정을 반복한다.

1. 루트 노드가 같은 경우 사이클이 발생한 것이다.
2. 루트 노드가 다른 경우 두 노드에 대해 union 연산을 수행한다.

 

처음엔 위 설명에 대해 이해되지 않았지만, 예제를 보며 이해가 됐다.

아래 예제를 통해 쉽게 이해해보자.

 

예제

먼저 다음과 같이 각 그래프가 연결되어 있다고 하자.

edges = [(1, 2), (2, 3), (1, 3)]

 

연산 수행 전, 각 노드와 parent 배열의 상태는 아래와 같다.

 

이후 각각의 노드를 연결하면서, 사이클의 개수를 찾아보자.

• (1, 2) 연결
  두 노드를 연결(union)하는 과정에서, find 함수에 의해 parent[2]가 1로 업데이트 된다.

• (2, 3) 연결
  두 노드를 연결(union)하는 과정에서, find 함수에 의해 parent[3]이 1로 업데이트 된다.

• (1, 3) 연결
  두 노드를 연결(union)하면, 아래 그림과 같이 사이클이 발생하는 것을 알 수가 있다. 그 때의 parent[1]과 parent[3]이 같은 값을 가지는 것 또한 추가로 알 수 있다.
  
  따라서 위에서 사이클을 판별할 때, 연결(union)하려는 두 노드의 parent가 같은지, 아닌지에 따라 사이클을 판별하는 이유도 해당 예제와 같은 이유 때문이다.

 

📂 기본 예제 코드(Python)

아래 코드는 사이클의 개수를 찾는 코드이다.

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

def union(parent, x, y):
    x = find(parent, x)
    y = find(parent, y)
    
    if x < y:
        parent[y] = x
    else:
        parent[x] = y
    
def solution(n, edges):
    cycle = 0
    parent = [i for i in range(n)]
    for x, y in edges:
        if find(parent, x) == find(parent, y):
            cycle += 1
        
        union(parent, x, y)

    return cycle

edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 2), (3, 0)]
print(solution(5, edges))