12.6 깊이 우선 탐색(DFS)

1. DFS의 개요

깊이 우선 탐색(Depth-First Search, DFS)은 그래프 탐색의 또 다른 기본 알고리즘이며, 가능한 한 깊이 들어간 후 더 이상 진행할 수 없을 때 백트래킹(backtracking)하는 방식으로 그래프를 탐색한다. 스택(또는 재귀 호출)을 사용하여 노드를 관리한다. DFS는 사이클 검출, 위상 정렬, 강하게 연결된 컴포넌트 발견, 다리와 절단점 찾기 등 그래프의 구조적 분석에 매우 유용하다. 로봇공학에서는 작업 의존성 분석, 미로 탐색, 운동 계획의 트리 탐색 등에 활용된다.

2. 알고리즘의 핵심 아이디어

2.1 깊이 우선의 의미

DFS의 “깊이 우선“은 한 경로를 끝까지 따라간 후 다른 경로를 탐색한다는 의미이다. 시작 노드에서 출발하여 미방문 이웃이 있는 한 계속 깊이 들어간다.

2.2 백트래킹

더 이상 진행할 수 없는 막다른 골목에 도달하면 가장 최근의 분기점으로 돌아가서 다른 경로를 탐색한다. 이를 백트래킹이라 한다.

2.3 스택의 역할

스택은 LIFO(Last In, First Out) 원칙을 따른다. DFS에서 스택은 가장 최근에 발견된 노드를 우선적으로 처리하는 효과를 만든다.

3. 알고리즘의 구체적 설명

3.1 재귀적 의사 코드

DFS(G):
    for each node v in G:
        v.color = WHITE
        v.parent = None
    time = 0
    for each node v in G:
        if v.color == WHITE:
            DFS_visit(G, v)

DFS_visit(G, v):
    time = time + 1
    v.discovery_time = time
    v.color = GRAY
    
    for each neighbor u of v:
        if u.color == WHITE:
            u.parent = v
            DFS_visit(G, u)
    
    v.color = BLACK
    time = time + 1
    v.finish_time = time

3.2 반복적 의사 코드

DFS_iterative(G, s):
    visited = {s}
    stack = [s]
    
    while stack is not empty:
        v = stack.pop()
        process(v)
        for each neighbor u of v:
            if u not in visited:
                visited.add(u)
                stack.push(u)

3.3 노드의 색

DFS의 분석에서 노드는 세 가지 색으로 분류된다.

흰색(WHITE): 아직 발견되지 않음
회색(GRAY): 발견되었지만 아직 처리 중(이웃을 검사 중)
검은색(BLACK): 처리가 완료됨

이 색 분류는 사이클 검출 등의 응용에서 활용된다.

3.4 발견 시간과 종료 시간

DFS는 각 노드에 두 개의 시간을 할당한다.

발견 시간(discovery time): 노드가 처음 발견되는 시점
종료 시간(finish time): 노드의 처리가 완료되는 시점

이러한 시간 정보는 위상 정렬, 강하게 연결된 컴포넌트 등의 알고리즘에서 사용된다.

4. 시간 복잡도와 공간 복잡도

4.1 시간 복잡도

DFS의 시간 복잡도는 BFS와 같다.

인접 리스트: $O(|V| + |E|)$
인접 행렬: $O(|V|^2)$

각 노드는 한 번 방문되고, 각 엣지는 한 번 검사된다.

4.2 공간 복잡도

DFS의 공간 복잡도는 $O(|V|)$ 이다. 다만 재귀적 구현에서는 재귀 스택의 깊이가 그래프의 깊이에 비례하므로, 매우 깊은 그래프에서는 스택 오버플로우의 위험이 있다.

5. DFS 트리와 엣지의 분류

5.1 DFS 트리

DFS는 그래프 위에 트리를 구성한다. 각 노드의 부모는 그 노드를 발견한 노드이다. 이를 DFS 트리라 한다.

5.2 엣지의 분류

DFS는 그래프의 엣지를 네 가지로 분류한다.

5.2.1 트리 엣지(Tree Edge)

DFS 트리에 포함된 엣지이다. $u$ 가 $v$ 를 발견하는 데 사용된 엣지 $(u, v)$ 가 트리 엣지이다.

5.2.2 백 엣지(Back Edge)

조상으로 향하는 엣지이다. $(u, v)$ 에서 $v$ 가 $u$ 의 조상이면 백 엣지이다. 백 엣지의 존재가 사이클을 의미한다.

5.2.3 전진 엣지(Forward Edge)

후손으로 향하는 비트리 엣지이다. $(u, v)$ 에서 $v$ 가 $u$ 의 후손이지만 트리 엣지가 아닌 경우이다.

5.2.4 교차 엣지(Cross Edge)

조상-후손 관계가 아닌 엣지이다. 다른 부분 트리의 노드를 향한다.

방향 그래프에서는 네 종류 모두 가능하지만, 무방향 그래프에서는 트리 엣지와 백 엣지만 존재한다.

6. DFS의 주요 응용

6.1 사이클 검출

DFS는 그래프의 사이클 검출에 매우 효과적이다.

6.1.1 무방향 그래프

무방향 그래프에서는 백 엣지의 존재가 사이클을 의미한다. 부모 노드를 제외한 인접 노드 중 회색인 노드가 있으면 사이클이다.

def has_cycle_undirected(G):
    visited = set()
    
    def dfs(v, parent):
        visited.add(v)
        for u in G[v]:
            if u not in visited:
                if dfs(u, v):
                    return True
            elif u != parent:
                return True
        return False
    
    for v in G.nodes:
        if v not in visited:
            if dfs(v, None):
                return True
    return False

6.1.2 방향 그래프

방향 그래프에서는 색을 사용하여 백 엣지를 검출한다.

def has_cycle_directed(G):
    color = {v: 'white' for v in G.nodes}
    
    def dfs(v):
        color[v] = 'gray'
        for u in G[v]:
            if color[u] == 'gray':
                return True  # 백 엣지
            if color[u] == 'white' and dfs(u):
                return True
        color[v] = 'black'
        return False
    
    for v in G.nodes:
        if color[v] == 'white':
            if dfs(v):
                return True
    return False

6.2 위상 정렬

방향 비순환 그래프(DAG)의 위상 정렬은 DFS의 종료 시간의 역순으로 노드를 나열한 것이다.

def topological_sort(G):
    visited = set()
    order = []
    
    def dfs(v):
        visited.add(v)
        for u in G[v]:
            if u not in visited:
                dfs(u)
        order.append(v)
    
    for v in G.nodes:
        if v not in visited:
            dfs(v)
    
    return order[::-1]

위상 정렬은 작업의 의존성을 만족하는 실행 순서를 결정한다.

6.3 강하게 연결된 컴포넌트

방향 그래프의 강하게 연결된 컴포넌트(Strongly Connected Component, SCC)를 찾는 알고리즘에는 다음이 있다.

6.3.1 Kosaraju 알고리즘

원래 그래프에서 DFS를 수행하고 종료 시간을 기록한다.
그래프의 모든 엣지를 뒤집는다.
종료 시간의 역순으로 뒤집힌 그래프에서 DFS를 수행한다. 각 DFS 호출이 하나의 SCC이다.

6.3.2 Tarjan 알고리즘

Tarjan 알고리즘은 단일 DFS로 SCC를 찾는다. 각 노드의 발견 시간과 lowlink 값을 사용한다.

6.4 다리와 절단점

6.4.1 다리

엣지를 제거했을 때 그래프가 분리되는 엣지를 다리(bridge)라 한다. DFS로 효율적으로 찾을 수 있다.

6.4.2 절단점

노드를 제거했을 때 그래프가 분리되는 노드를 절단점(articulation point) 또는 cut vertex라 한다. DFS로 찾을 수 있다.

이러한 개념은 네트워크의 취약점 분석에 사용된다.

6.5 경로 찾기

DFS는 두 노드 사이의 경로를 찾는 데 사용될 수 있다(최단 경로는 보장하지 않음).

def find_path_dfs(G, s, t, path=None):
    if path is None:
        path = [s]
    if s == t:
        return path
    for u in G[s]:
        if u not in path:
            new_path = find_path_dfs(G, u, t, path + [u])
            if new_path:
                return new_path
    return None

7. DFS와 BFS의 비교

7.1 방문 순서

측면	DFS	BFS
자료 구조	스택 (LIFO)	큐 (FIFO)
방문 순서	깊이 우선	너비 우선
메모리	깊이에 비례	너비에 비례
최단 경로	보장 안 함	비가중치에서 보장
자연스러운 응용	사이클, 위상 정렬	최단 경로, 레벨

7.2 적합한 응용

7.2.1 DFS가 적합한 경우

그래프의 구조적 분석 (사이클, 컴포넌트)
위상 정렬
백트래킹 문제
메모리 제약이 있는 깊은 그래프

7.2.2 BFS가 적합한 경우

비가중치 최단 경로
레벨 순회
가까운 이웃 탐색

8. 재귀와 반복의 비교

8.1 재귀적 구현

재귀적 구현은 코드가 단순하고 직관적이다. 그러나 재귀 깊이가 시스템 스택의 크기에 의해 제한된다.

def dfs_recursive(G, v, visited):
    visited.add(v)
    for u in G[v]:
        if u not in visited:
            dfs_recursive(G, u, visited)

8.2 반복적 구현

반복적 구현은 명시적 스택을 사용한다. 시스템 스택의 제약을 받지 않으며, 매우 깊은 그래프에도 적용할 수 있다.

def dfs_iterative(G, s):
    visited = {s}
    stack = [s]
    while stack:
        v = stack.pop()
        for u in G[v]:
            if u not in visited:
                visited.add(u)
                stack.append(u)

다만 반복적 구현에서 발견 시간과 종료 시간을 정확히 추적하려면 추가 작업이 필요하다.

9. DFS의 변형

9.1 깊이 제한 DFS

깊이 제한 DFS(Depth-Limited DFS)는 일정 깊이까지만 탐색한다. 무한 깊이 그래프에서 사용된다.

def dfs_limited(G, v, limit, visited=None):
    if visited is None:
        visited = set()
    if limit < 0:
        return
    visited.add(v)
    for u in G[v]:
        if u not in visited:
            dfs_limited(G, u, limit - 1, visited)

9.2 반복 깊이 우선 탐색

반복 깊이 우선 탐색(Iterative Deepening DFS, IDDFS)은 깊이 제한을 점진적으로 증가시키며 깊이 제한 DFS를 반복한다. BFS의 메모리 효율성과 DFS의 최적성을 결합한다.

def iddfs(G, s, t):
    depth = 0
    while True:
        result = dls(G, s, t, depth)
        if result is not None:
            return result
        depth += 1

9.3 양방향 DFS

양방향 DFS는 시작과 목표에서 동시에 DFS를 수행한다. BFS의 양방향 변형보다 일반적이지 않다.

10. DFS의 구체적 응용

10.1 미로 탐색

미로의 입구에서 출구까지 경로를 찾을 때 DFS가 자연스럽다. 백트래킹으로 막다른 골목을 처리한다.

10.2 백트래킹 문제

8-퀸 문제, 스도쿠, n-퀸 문제 등 백트래킹 알고리즘은 본질적으로 DFS의 변형이다.

10.3 컴파일러

컴파일러의 의존성 분석, 함수 호출 그래프 분석 등에 DFS가 사용된다. 재귀 함수 검출도 DFS로 가능하다.

10.4 게임 트리 탐색

체스, 바둑 등 게임의 가능한 수의 트리를 탐색하는 데 DFS와 그 변형(미니맥스, 알파-베타 가지치기)이 사용된다.

10.5 의존성 해결

소프트웨어 패키지의 의존성 해결에 DFS와 위상 정렬이 사용된다.

11. 로봇공학에서의 응용

11.1 운동 계획

샘플링 기반 운동 계획(예: RRT)에서 트리를 확장하는 과정이 DFS의 변형이다.

11.2 작업 계획

로봇의 작업이 의존성을 가질 때 DFS와 위상 정렬로 실행 순서를 결정한다.

11.3 매니퓰레이터의 운동학

매니퓰레이터의 트리 구조에서 운동학과 동역학 계산이 DFS의 형태로 진행된다.

11.4 환경 탐색

미지의 환경에서 로봇이 모든 영역을 탐색할 때 DFS가 활용된다. 깊이 있게 한 경로를 따라간 후 백트래킹한다.

11.5 그래프 SLAM

그래프 SLAM에서 회로 폐쇄 검증, 그래프의 구조 분석 등에 DFS가 사용된다.

12. 응용 예시: 작업 스케줄링

매니퓰레이터가 여러 작업을 수행할 때 작업 사이에 의존성이 있을 수 있다. 예를 들어 A 작업이 B 작업보다 먼저 수행되어야 한다는 식이다. 이러한 의존성을 방향 그래프로 표현하고 위상 정렬을 적용하면 작업의 실행 순서가 결정된다.

def schedule_tasks(tasks, dependencies):
    G = {t: [] for t in tasks}
    for a, b in dependencies:
        G[a].append(b)
    return topological_sort(G)

13. 응용 예시: 사이클이 있는 의존성 검출

작업 의존성에 사이클이 있으면 실행 순서를 결정할 수 없다. DFS로 사이클을 검출하여 사용자에게 경고한다.

14. 응용 예시: 미로의 모든 경로 탐색

미로의 입구에서 출구까지의 모든 경로를 찾을 때 DFS가 사용된다. 백트래킹으로 모든 가능성을 탐색한다.

15. 응용 예시: 컴포넌트 분석

로봇이 활동하는 환경이 여러 분리된 영역으로 구성될 수 있다. DFS로 각 영역(연결 컴포넌트)을 식별한다.

16. 응용 예시: SLAM 그래프 분석

그래프 SLAM에서 그래프의 연결성을 검사하거나, 강하게 연결된 부분을 찾는 데 DFS가 사용된다.

17. 성능 최적화

17.1 재귀 깊이 제한

매우 깊은 그래프에서는 재귀 깊이 제한이 문제가 될 수 있다. Python의 경우 sys.setrecursionlimit()로 제한을 늘릴 수 있지만, 반복적 구현이 더 안전하다.

17.2 명시적 스택

반복적 구현에서 명시적 스택을 사용하면 깊이 제한 없이 동작한다. 메모리 사용도 명확하게 제어할 수 있다.

17.3 발견 표시 자료 구조

발견 표시는 해시 셋이 일반적이지만, 노드 ID가 정수이면 비트 배열이 더 효율적일 수 있다.

18. DFS의 라이브러리 지원

18.1 NetworkX

import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4)])

# DFS 트리
T = nx.dfs_tree(G, source=1)

# DFS 엣지 순회
for edge in nx.dfs_edges(G, source=1):
    print(edge)

# DFS 후순서
for v in nx.dfs_postorder_nodes(G, source=1):
    print(v)

# 위상 정렬
order = list(nx.topological_sort(G))

# 사이클 검출
try:
    cycle = nx.find_cycle(G)
    print("Cycle found:", cycle)
except nx.NetworkXNoCycle:
    print("No cycle")

18.2 다른 라이브러리

igraph
Boost Graph Library
graph-tool

19. 학습의 가치

DFS를 깊이 이해하는 것은 다음과 같은 이점을 제공한다.

그래프의 구조적 분석을 수행할 수 있다.
사이클, 위상 정렬, 컴포넌트 등의 문제를 해결할 수 있다.
백트래킹 알고리즘의 기초를 형성한다.
재귀적 사고를 익힌다.
게임 AI와 인공지능 알고리즘의 기초를 이해한다.

20. 학습 권장사항

20.1 직접 구현

DFS를 재귀적, 반복적으로 모두 구현해 본다. 두 형태의 차이를 이해한다.

20.2 응용 학습

사이클 검출, 위상 정렬, 컴포넌트 등의 응용을 직접 구현해 본다.

20.3 시각화

DFS의 단계별 시각화는 알고리즘의 동작을 이해하는 데 도움이 된다. 노드의 색 변화, 발견 시간, 종료 시간 등이 시각화된다.

21. 본 절의 의의

본 절은 그래프 알고리즘의 또 다른 핵심인 DFS를 자세히 다루었다. DFS는 그래프의 구조적 분석에 매우 유용하며, 위상 정렬, 사이클 검출, 컴포넌트 발견 등 다양한 응용의 기초이다. BFS와 함께 그래프 알고리즘의 양대 축을 이룬다.

22. 참고 문헌

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.
Tarjan, R. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146–160.
Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.

version: 1.0