사이클 탐지(Cycle detection)

30 Mar 2025 in Blog / 알고리즘

• 그러면 사이클 탐지에 관해 총 3가지 알고리즘을 통해 알려줄게
• DFS 기반 사이클 탐지
  • 방향 그래프 (Directed Graph)
  • 무방향 그래프 (Undirected Graph)
  • DFS 기반 방향과 무방향 그래프 사이클 탐지의 차이점
• 위상 정렬(Topological Sort) 기반 사이클 탐지
  • 진입 차수 위상 정렬(In-degree Topological Sort) 기반 사이클 탐지 함수
  • 위상정렬과 DFS 기반 사이클 탐지 비교
• Disjoint Set / Union-Find 기반 사이클 탐지
  • 경로 압축(Path Compression)
  • 랭크 최적화 (Union by Rank)
  • 경로 압축(Path Compression) 와 랭크 최적화 (Union by Rank) 요약표
  • Union-Find와 DFS 기반 사이클 탐지 비교
• 마무리

사이클(순환) 탐지는 그래프에서 매우 중요한 문제 중 하나야. 특히 방향 그래프(Directed Graph)에서 많이 다루고 사이클이 존재하면 예를 들어 작업 순서 정하기(Topological Sort) 같은 문제에서 큰 문제가 생기기 때문

아래는 사이클 탐지가 필요한 상황을 예로 들었어

• 작업 간 선후 관계 (예: A를 끝낸 후에 B를 해야 함)

• 종속성 관리 (패키지 설치 순서 등)

• 알고리즘 문제 (백준, 프로그래머스, 리트코드 등)

그러면 사이클 탐지에 관해 총 3가지 알고리즘을 통해 알려줄게

• DFS (방향/무방향)

• 위상 정렬 (방향)

• Disjoint Set / Union-Find (무방향)

DFS 기반 사이클 탐지

DFS는 그래프를 순회하면서 사이클이 있는지 확인하는 가장 기본적이고 널리 쓰이는 방법 중 하나로써, DFS(깊이 우선 탐색)는 그래프를 탐색할 때, 가능한 한 깊이 들어가며 노드를 방문하는 방식이야. 사이클 탐지에서는 이 DFS 경로에서 이미 방문했던 노드를 다시 만나는 경우, 조건에 따라 그것이 사이클인지 판단할 수 있어.

DFS 기반 같은 경우 그래프가 적당히 작거나 중간 크기일 때, 방향 그래프인지 무방향 그래프인지 확실히 구분될 때, 빠르게 구현하고 싶을 때 사용하면 좋아

방향 그래프 (Directed Graph)

사이클 판단 기준이 ‘현재 DFS 경로 상에 이미 있는 노드를 다시 방문’했을 때야.

• visited: 이 노드를 한번이라도 방문했는지, 이미 한 번이라도 본 노드

• rec_stack: 현재 DFS 경로에 있는 노드인지 (재귀 스택), “지금 내가 밟고 있는 길”

def has_cycle(graph): # graph를 함수에 적용
    visited = set() # visited라는 중복 없는 요소들의 모음 생성
    rec_stack = set() # rec_stack라는 중복 없는 요소들의 모음 생성

    def dfs(node):
        visited.add(node) # visited에 node 추가
        rec_stack.add(node) # rec_stack에 node 추가

        for neighbor in graph[node]: # 노드의 이웃들중 하나씩
            if neighbor not in visited: # visited에 없으면
                if dfs(neighbor): # neighbor와 함께 dfs 함수를 실행시켰을시 True가 반환된다면
                    return True # true 반환
            elif neighbor in rec_stack: # visited에 없고 rec_stack에 있으면
                return True  # 사이클 발견

        rec_stack.remove(node)
        return False

    for node in graph: # 그래프의 모든 노드들중 하나씩
        if node not in visited: # visited 모음에 없다면
            if dfs(node): # node와 함께 dfs 함수를 실행시킨다
                return True

    return False

graph = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A'],  # A -> B -> C -> A (사이클)
}
print(has_cycle(graph))  # True

위에서 첫번째 for문이 햇갈릴 수 있는데, 아래와 같이 생각해보면 쉬워

A → B → C
    ↑   ↓
     ←--

DFS 순서 :

• dfs(A) → 방문: A, 재귀 스택: A

• dfs(B) → 방문: A,B, 재귀 스택: A,B

• dfs(C) → 방문: A,B,C, 재귀 스택: A,B,C

• C의 이웃이 A인데, A는 이미 재귀 스택에 있음! 👉 지금 내가 왔던 길을 다시 돌아가고 있으니 사이클!

무방향 그래프 (Undirected Graph)

이번엔 단순히 DFS 중 이미 방문한 노드를 다시 만난 경우라고 해도, 그게 바로 이전 노드(부모)라면 사이클이 아님. 그래서 “부모 노드 제외” 조건이 중요해.

• visited: 방문 여부

• parent: 현재 노드를 호출한 부모 노드

def has_cycle_undirected(graph): # graph를 함수에 넣고 시작
    visited = set() # visited라는 중복 없는 요소들의 모음 생성

    def dfs(node, parent):
        visited.add(node) # visited에 원소를 추가하고
        for neighbor in graph[node]: # 그 원소의 모든 이웃들 하나씩
            if neighbor not in visited: # visited 에 없다면
                if dfs(neighbor, node): # dfs에 이웃과 자신을 부모로 실행
                    return True # 위 함수 실행결과 True 라면 True 반환
            elif neighbor != parent: # dfs(A, C) 실행시 여기까지 오고 조건문 충족됨
                return True  # 사이클 발견

        return False

    for node in graph: #graph 안에 모든 노드 중 하나씩
        if node not in visited: # visited에 없다면
            if dfs(node, None): # 자기 자신과 None을 갖고 함수 실행하고 함수 실행결과 True라면
                return True # True 반환

    return False

graph = {
    'A': ['B'],
    'B': ['A', 'C'],
    'C': ['B', 'A'],  # A - B - C - A (사이클)
}
print(has_cycle_undirected(graph))  # True

방향 그래프와 크게 차이가 나진 않는것 같지만, 무방향 그래프는 parent 도입해서 사이클을 찾아냈다.

A → B → C
↑       ↓
←───────

• dfs(A, None)

• dfs(B, A)

• dfs(C, B)

• dfs(A, C), 여기서 A가 C와 다르기 때문에 cycle이 탐지됨

DFS 기반 방향과 무방향 그래프 사이클 탐지의 차이점

• 방향 그래프에서는 재귀 스택(rec_stack)을 꼭 써야 함!

• 무방향 그래프에서는 parent 추적이 없으면 무조건 사이클로 잘못 판단함

위상 정렬(Topological Sort) 기반 사이클 탐지

위상 정렬(Topological Sort)은 방향 그래프에서 노드들의 선후 관계를 정렬하는 알고리즘이야. 이전에 한번 다루긴 했는데, 위상정렬을 할려면 사이클이 없는 그래프여야 해. 고로 위상 정렬이 실패한다면 → 사이클이 있다는 뜻이지!

핵심 원리는 아래와 같아

• 모든 노드의 진입 차수(in-degree)를 센다. (들어오는 간선 수)

• 진입 차수가 0인 노드를 큐에 넣고 하나씩 꺼내며 줄여 나감

• 만약 큐가 비었는데 아직 처리 못 한 노드가 있다면, 그건 사이클 안에 갇힌 노드란 뜻! → 사이클 존재!

간단한 예시를 아래에 들게

A → B → C
↑       ↓
←───────

• 진입 차수: A(1), B(1), C(1)

• 진입 차수 0인 노드가 없어 → 시작 자체가 안 됨 → 사이클 있음!

그러면 함수로 넘어가 보자

진입 차수 위상 정렬(In-degree Topological Sort) 기반 사이클 탐지 함수

from collections import deque, defaultdict 

def has_cycle_topo_sort(graph): # graph를 함수에 사용
    in_degree = defaultdict(int) # defaultdict으로 기본값 자동 0으로 지정해주는 딕셔너리

    # 진입 차수 계산
    for node in graph: # 그래프의 모든 노드중 하나씩
        for neighbor in graph[node]: # 노드의 모든 이웃중 하나씩
            in_degree[neighbor] += 1 # 처음 보는 노드 자동으로 0부터 시작, 진입 차수 1씩 증가

    # 진입 차수 0인 노드부터 시작
    queue = deque([node for node in graph if in_degree[node] == 0])

    visited_count = 0 # 카운트용 변수 0으로 시작

    while queue: # 큐에 값이 있을때
        current = queue.popleft() # current에 큐 pop한것을 저장, 큐 -1
        visited_count += 1 # count 1 증가

        for neighbor in graph[current]: # current의 모든 이웃들 중 하나씩
            in_degree[neighbor] -= 1 # 이웃의 진입 차수를 1 감소 시킨다
            if in_degree[neighbor] == 0: # 이웃의 진입 차수가 0이 되면
                queue.append(neighbor) # q에 추가한다

    # 모든 노드를 방문했는가? (방문 못했으면 사이클)
    return visited_count != len(graph)

graph = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A'],  # 사이클 A -> B -> C -> A
}
print(has_cycle_topo_sort(graph))  # True

위상정렬과 DFS 기반 사이클 탐지 비교

항목	DFS 방식	위상 정렬 방식
방향 그래프	O	O
사이클 경로 찾기	가능	어려움
정렬 순서 제공	X	가능
직관성	쉬움	약간 복잡
성능	보통	효율적 (큐 기반)

Disjoint Set / Union-Find 기반 사이클 탐지

무방향 그래프에서 아주 빠르게 사이클을 찾는데 유용한 탐지법이다.

• 여러 개의 서로소 집합(disjoint set)을 관리하는 자료구조야.

• 각 노드는 하나의 집합에 속함

• 주로 두 노드가 같은 집합에 속해 있는지를 확인하고, 합치기(union)도 할 수 있어

무방향 그래프에서 두 노드가 이미 같은 집합에 있는데, 다시 그 둘을 연결하는 간선이 있다면 사이클이 생긴다!

• 각 노드는 어떤 그룹(집합)에 속해 있어.

• 간선을 연결할 때마다, 두 노드가 같은 그룹이면 → 이미 연결돼 있다는 뜻 → 사이클

• 다른 그룹이면 → 그룹을 합치면 됨 (union)

# 부모 노드를 저장하는 딕셔너리
parent = {}

# find: 루트 노드 찾기
def find(x):
    if parent[x] != x: # parent[x] 와 x의 값이 같지 않을 때, 두번째 값 parent[B] != A 일때
        parent[x] = find(parent[x])  # 경로 압축, parent[B] = find(parent[B]) = find(A) = parent[A] = A
    return parent[x]

# union: 두 노드 연결
def union(x, y):
    root_x = find(x) # 처음엔 x 반환, 두번째에는 A 반환, 세번째에도 A 반환
    root_y = find(y) # 처음엔 y 반환, 두번째에는 C 반환 , 세번째에는 A 반환
    if root_x == root_y: # root_x 와 root_y가 같을 때
        return False  # 사이클 발생!
    parent[root_y] = root_x # 같지 않다면 parent[root_y] 값에 root_x 저장.
    return True             # parent[B] = A, parent[C] = A,

def has_cycle_union_find(edges): # edges로 함수 실행
    for u, v in edges: # edges의 모든 원소의 시작점과 마지막점 하나씩
        # 초기화
        if u not in parent: # u가 parent에 없다면
            parent[u] = u # parent[u] 값에 u 저장
        if v not in parent: # v가 parent에 없다면
            parent[v] = v # parent[v] 값에 v 저장

        if not union(u, v): # u와 v값으로 union 함수 실행
            return True  # 사이클 발견!

    return False

edges = [
    ('A', 'B'),
    ('B', 'C'),
    ('C', 'A'),  # 이 간선이 사이클을 만듦!
]

print(has_cycle_union_find(edges))  # True

경로 압축(Path Compression)

Disjoint Set / Union-Find에서 아래 함수가 햇갈리지 않아?

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

find(x)를 호출할 때, x의 부모를 따라 루트까지 올라가잖아? 그 루트를 찾은 김에 거치는 모든 노드들을 바로 루트에 연결시켜줘! 다음에 find()할 때 훨씬 빠르게 찾을 수 있어.

• 경로 압축 전

  A → B → C → D (루트)
  

• 경로 압축 후

  A → D
  B → D
  C → D
  

find(A) 다시 하면 → 바로 D!

랭크 최적화 (Union by Rank)

두 집합을 합칠 때, 그냥 막 합치면 트리가 한쪽으로 기울어져서 느려질 수 있어 → 그래서 작은 트리를 큰 트리 밑에 붙이는 방식으로 트리 높이를 최소화할 때 쓰는 랭크 최적화 설명해줄게

각 루트 노드의 “랭크(rank)” (트리 높이 비슷한 개념)를 저장하는 딕셔너리를 하나 둬!

rank = {}

아래는 Union 구현(랭크 최적화 포함) 함수야

if u not in parent:
    parent[u] = u
    rank[u] = 0

def union(x, y):
    root_x = find(x)
    root_y = find(y)

    if root_x == root_y:
        return False  # 사이클

    # 더 랭크가 낮은 트리를 높은 트리 밑에 붙인다
    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        parent[root_y] = root_x # 처음에 이렇게 될 텐데, rank 값이 같다면, root_x가 parent가
        rank[root_x] += 1       # 되면서, rank도 1 증가

    return True

예제 : 간선 연결 순서

edges = [
    ('A', 'B'),
    ('B', 'C'),
    ('C', 'D'),
    ('D', 'E'),
]

union(‘A’, ‘B’) 했을 시

parent['A'] = 'A'
parent['B'] = 'B'
rank['A'] = 0
rank['B'] = 0

두 랭크가 같다면, A가 root가 되고 A의 랭크 += 1

parent = {'A': 'A', 'B': 'A'}
rank   = {'A': 1, 'B': 0}

union(‘B’, ‘C’) 했을 시

• find(B) → A (경로 압축)

• C는 초기화: parent[‘C’] = ‘C’, rank[‘C’] = 0

• rank[A] = 1, rank[C] = 0 → C를 A 밑에 붙임

parent = {'A': 'A', 'B': 'A', 'C': 'A'}
rank   = {'A': 1, 'B': 0, 'C': 0}

경로 압축(Path Compression) 와 랭크 최적화 (Union by Rank) 요약표

최적화 기법	효과	구현 방법
Path Compression	find() 속도 향상 (트리 납작하게 만듦)	find() 재귀 후, 부모 갱신
Union by Rank	union() 속도 향상 (트리 높이 줄임)	랭크 비교해서 낮은 쪽을 붙임

이 두가지 기법을 사용하면 거의 O(1)에 가까운 속도로 사이클을 탐지할 수 있어

Union-Find와 DFS 기반 사이클 탐지 비교

항목	Union-Find 방식	DFS 기반 방식
✅ 아이디어	같은 집합에 있는 노드를 다시 연결하려 하면 사이클 발생	이미 방문한 이웃이 부모가 아니라면 사이클
🔁 탐색 방식	간선 중심 (edge list 기반)	노드 중심 (DFS 순회)
🔧 구현 난이도	조금 복잡 (find/union 필요)	비교적 간단
💡 자료구조	parent, rank 딕셔너리	visited + 재귀 호출
⚡ 성능	매우 빠름 (거의 O(1) per edge)	O(V + E), 보통은 충분히 빠름
📦 사용 전제	무방향 그래프 + 간선 리스트 필요	무방향 그래프만 있으면 가능
🔍 사이클 경로 추적	어려움 (사이클 있음 여부만 확인)	상대적으로 추적 쉬움
🌲 트리 구조 유지	트리 병합하며 유지	DFS 트리 만들 수 있음

Union-Find는

• 간선 연결 시 “너희 둘 이미 같은 집단 아니야?”만 체크, 사이클 유무만 초고속으로 판단하고 싶을 때 최적

DFS는

• 재귀적으로 “내가 왔던 부모 빼고, 다른 방문 노드 만나면 사이클!”을 판별, 사이클 경로를 추적하고 싶거나, DFS 트리 자체가 필요한 상황에 유리

마무리

방법	그래프 종류	주요 아이디어	장점	비고
DFS + visited + rec_stack	방향 그래프	재귀 경로 추적	직관적, 간단
DFS + 부모 체크	무방향 그래프	부모 제외하고 방문 확인	단순한 구현
위상 정렬 (Kahn)	방향 그래프	진입 차수 0 제거	정렬 결과도 얻음	전체 노드 방문 확인
Union-Find	무방향 그래프	같은 집합이면 사이클	빠름	방향 X