[100일의 IT 초보 탈출] #58 유니온 파인드 _ 그래프 안에 사이클이 있을까?

오늘은 무엇을 배우게 될까요?

 

그래프 알고리즘에서 때때로 중요한 질문이 있습니다.

 

이 연결 구조 안에 순환(Cycle)이 있을까?

 

이 질문에 답할 수 있어야

위상 정렬을 적용할 수 있는지 판단하고 그래프가 트리 구조인지 검증하고 네트워크 상 충돌 여부나 의존 관계의 모순을 확인할 수 있습니다.

 

오늘은 사이클이 있는지 효율적으로 판별하는 알고리즘인

유니온 파인드 (Union-Find, 서로소 집합)을 배워봅니다.

 

---

 

유니온 파인드란?

 

서로소 집합(Disjoint Set)은

여러 개의 원소를 그룹으로 묶되, 서로 겹치지 않게 관리할 수 있도록 하는 자료구조입니다.

 

두 노드를 연결할 때 사이클이 생기는지 확인하는 데에 특히 유용합니다.

 

---

기본 원리

연산설명

Find(x)	x가 속한 집합(부모 노드)을 찾는다
Union(x, y)	x와 y가 속한 집합을 합친다 (한쪽을 다른 쪽 부모로 연결)

 

사이클 탐지 방법

 

• 두 노드를 Union하기 전에 Find로 부모를 비교
• 부모가 같다면 → 이미 연결된 집합이므로 사이클 발생

 

---

실전 예시

# 부모 테이블 초기화
parent = [i for i in range(6)]

# Find 함수
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

# Union 함수
def union(a, b):
    a_root = find(a)
    b_root = find(b)
    if a_root == b_root:
        return False  # 사이클 발생
    parent[b_root] = a_root
    return True

# 간선 정보
edges = [(0, 1), (1, 2), (2, 3), (1, 3), (4, 5)]

# 사이클 여부 확인
cycle_found = False
for a, b in edges:
    if not union(a, b):
        cycle_found = True
        print(f"사이클 발생: {a}-{b}")
        break

if not cycle_found:
    print("사이클 없음")

출력

사이클 발생: 1-3

 

---

시간 복잡도

연산시간

Find	O(α(N)) (거의 상수 시간)
Union	O(α(N))
→ α는 아커만(Ackermann) 함수의 역함수로, 매우 느리게 증가 → 거의 O(1)

 

---

유니온 파인드의 주요 응용

분야활용 예시

사이클 탐지	그래프가 트리인지 확인
네트워크 연결	연결 여부 확인
친구 관계	같은 그룹인지 확인
최소 신장 트리 (MST)	크루스칼 알고리즘에서 사용
게임 서버	길드/클랜/파벌 관리

 

---

유니온 파인드 vs DFS 사이클 탐지

사용 대상	무방향 그래프	방향/무방향 모두 가능
구현 난이도	간단하고 빠름	복잡한 경우 있음
구조 요구	서로소 집합	재귀적 탐색 구조
시간 효율	매우 효율적	노드 수에 따라 증가

 

---

한 줄 요약

 

👉 유니온 파인드는 그래프 구조에서 효율적으로 사이클을 탐지하는 알고리즘이며,

집합의 부모를 추적하는 방식으로 연결 상태를 빠르게 파악합니다.