깊이 우선 탐색 (DFS, Depth-First Search)

adulty22 2024. 9. 11. 20:06

깊이 우선 탐색 (DFS, Depth-First Search) 개요

깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 그래프의 모든 노드를 깊이(depth)를 우선으로 탐색하는 방법이다. DFS는 재귀(Recursion)나 스택(Stack)을 사용하여 구현할 수 있으며, 그래프 또는 트리에서 특정 경로를 찾거나, 모든 노드를 방문하는 데 유용하게 사용된다.

DFS는 다음과 같은 방식으로 동작한다:

시작 노드에서 출발하여 한 노드를 선택하고, 그 노드에서 갈 수 있는 경로 중 하나를 선택해 탐색을 계속 진행한다.
더 이상 갈 수 있는 노드가 없을 때, 다시 이전 경로로 돌아와 다른 경로를 탐색한다.
방문한 노드를 다시 방문하지 않도록 하기 위해 방문 여부를 기록한다.

DFS는 깊이 우선이기 때문에 가능한 한 깊이 있는 경로로 계속 탐색하다가, 더 이상 갈 곳이 없으면 되돌아오는 방식으로 동작한다.

DFS의 동작 원리

시작 노드에서 탐색을 시작한다.
해당 노드를 방문 처리한다.
해당 노드와 연결된 이웃 노드 중 방문하지 않은 노드를 탐색한다.
더 이상 방문할 수 있는 이웃 노드가 없을 경우, 이전 노드로 되돌아가 다른 경로를 탐색한다.
그래프의 모든 노드를 방문할 때까지 이 과정을 반복한다.

DFS 탐색 순서 예시

다음 그래프를 DFS로 탐색한다고 가정해 보겠다.

0 -- 1
|    |
4 -- 2 -- 3

DFS 탐색 순서는 다음과 같다 (0번 노드를 시작점으로):

0 → 1 → 2 → 3 → 4

(DFS는 스택 기반으로 동작하므로 탐색 순서는 다를 수 있지만, 그래프의 구조에 따라 가능한 경로 중 하나이다.)

DFS 구현 방법

DFS는 스택을 기반으로 동작한다. 스택을 명시적으로 사용할 수도 있고, 재귀 함수의 함수 호출 스택을 사용하여 구현할 수도 있다.

재귀(Recursion)를 사용한 DFS:
- 재귀 함수를 사용하여 더 깊이 있는 노드를 계속 탐색하다가, 더 이상 방문할 노드가 없으면 함수가 종료되며, 이전 상태로 돌아간다.
스택(Stack)을 사용한 DFS:
- 명시적인 스택을 사용하여 노드를 하나씩 스택에 넣고, 그 노드를 방문 처리한 후, 인접 노드를 다시 스택에 추가하는 방식으로 동작한다.

DFS 구현 (재귀 방식)

다음은 재귀 방식으로 DFS를 구현한 코드이다. Python에서 인접 리스트로 그래프를 표현하고, DFS를 사용하여 그래프의 모든 노드를 탐색한다.

class Graph:
    def __init__(self):
        self.adj_list = {}  # 인접 리스트로 그래프 표현

    # 간선 추가 함수
    def add_edge(self, u, v):
        if u not in self.adj_list:
            self.adj_list[u] = []
        if v not in self.adj_list:
            self.adj_list[v] = []
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)  # 무방향 그래프일 경우

    # DFS 재귀 구현
    def dfs(self, node, visited):
        # 현재 노드를 방문 처리
        visited.add(node)
        print(node, end=" ")  # 방문한 노드 출력

        # 인접 노드들 중 방문하지 않은 노드들을 재귀적으로 탐색
        for cur_node in self.adj_list[node]:
            if cur_node not in visited:
                self.dfs(cur_node, visited)

    # 그래프 탐색을 시작하는 함수
    def dfs_start(self, start_node):
        visited = set()  # 방문한 노드를 저장하는 집합
        self.dfs(start_node, visited)

# 그래프 생성
graph = Graph()

# 간선 추가 (무방향 그래프)
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(2, 4)

# DFS 탐색 (0번 노드에서 시작)
graph.dfs_start(0)
# 0 1 2 3 4

이 코드에서 DFS는 노드 0에서 출발하여 가능한 경로로 끝까지 탐색한 뒤, 더 이상 탐색할 노드가 없으면 돌아와 다른 경로를 탐색한다.

DFS 구현 (스택 방식)

다음은 스택을 사용하여 DFS를 구현한 코드이다. 스택을 명시적으로 사용하여, 노드를 방문할 때마다 스택에 쌓고, 가장 최근에 방문한 노드부터 탐색을 이어 나가는 방식이다.

class Graph:
    def __init__(self):
        self.adj_list = {}  # 인접 리스트로 그래프 표현

    # 간선 추가 함수
    def add_edge(self, u, v):
        if u not in self.adj_list:
            self.adj_list[u] = []
        if v not in self.adj_list:
            self.adj_list[v] = []
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)  # 무방향 그래프일 경우

    # DFS 스택 기반 구현
    def dfs_iterative(self, start_node):
        visited = set() # 방문한 노드를 저장하는 집합
        stack = [start_node] # 스택에 시작 노드를 넣음

        while stack:
            node = stack.pop() # 스택에서 노드를 꺼냄
            if node not in visited:
                print(node, end=" ") # 방문한 노드 출력
                visited.add(node)

                # 인접한 노드들을 스택에 추가 (방문하지 않은 노드만)
                for cur_node in self.adj_list[node]:
                    if cur_node not in visited:
                        stack.append(cur_node)

# 그래프 생성
graph = Graph()

# 간선 추가 (무방향 그래프)
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(2, 4)

# DFS 탐색 (스택 기반, 0번 노드에서 시작)
graph.dfs_iterative(0)
# 0 4 2 3 1

위 코드는 DFS를 스택으로 구현한 것으로, 재귀 호출 없이도 DFS를 수행할 수 있다.

Recursion VS Stack

스택(Stack)과 재귀(Recursion)를 사용하여 DFS(깊이 우선 탐색, Depth-First Search)를 구현할 때 각각의 장단점이 있다. 두 가지 방법은 기본적으로 동일한 알고리즘을 사용하지만, 구현 방식과 메모리 사용, 성능 등에 차이가 있다.

1. 재귀(Recursion) 방식의 DFS

재귀는 함수가 자기 자신을 호출하여 반복적으로 그래프를 탐색하는 방식이다. 재귀 호출 스택을 사용하여 DFS의 깊이를 처리한다.

장점

간결하고 직관적인 코드: 재귀 방식은 매우 직관적이고 코드가 간결하다. 코드에서 명시적으로 스택을 관리할 필요가 없고, 함수 호출 스택을 이용해 자연스럽게 탐색이 진행되므로 알고리즘을 구현하기가 쉽다.
재귀의 본질: DFS는 스택을 사용하는 알고리즘이므로, 재귀는 내부적으로 함수 호출 스택을 사용하여 이를 구현합니다. 문제를 분할 정복처럼 해결할 때 적합하다.

단점

재귀 깊이 제한: 대부분의 프로그래밍 언어(특히 Python)는 재귀 깊이 제한이 있다. Python의 경우 기본 재귀 깊이 제한이 1,000번으로 설정되어 있다. 매우 깊은 그래프나 트리를 탐색할 경우 재귀 깊이를 초과하여 RecursionError가 발생할 수 있다. 이 문제는 깊이 우선 탐색(DFS)에서 종종 문제가 될 수 있다.
성능 및 메모리: 재귀 호출을 많이 사용하면, 함수 호출 스택을 지속적으로 쌓아야 하므로 함수 호출 오버헤드가 발생한다. 또한, 각 함수 호출은 메모리를 차지하므로 깊은 탐색에서는 스택 오버플로(Stack Overflow) 위험이 있다.
디버깅 어려움: 재귀 호출은 호출이 중첩되기 때문에, 디버깅이나 오류 추적이 어려울 수 있다. 특히 깊이 있는 탐색에서 호출 스택을 추적하는 것이 복잡해질 수 있다.

2. 스택(Stack) 방식의 DFS

스택을 명시적으로 사용하여 DFS를 구현하는 방식이다. 스택을 사용하여 그래프의 노드를 탐색하고, 재귀를 사용하지 않으므로 메모리 관리가 보다 명확하게 이루어진다.

장점

재귀 깊이 제한 없음: 스택 방식은 함수 호출이 아닌 명시적인 스택 자료구조를 사용하므로, 재귀 깊이 제한에 영향을 받지 않는다. 매우 깊은 그래프를 탐색할 때 재귀보다 안전하다. 스택에 너무 많은 노드가 쌓이면 메모리 부족 위험은 여전히 있지만, 재귀 깊이 제한이 없는 점에서 유리하다.
메모리 제어 가능: 스택을 명시적으로 관리할 수 있으므로, 메모리 사용을 제어하고 최적화할 수 있다. 예를 들어, 필요하지 않은 노드를 스택에서 즉시 제거하는 등의 작업을 쉽게 할 수 있다.
디버깅 용이성: 스택 기반 DFS는 함수 호출의 중첩이 없기 때문에 디버깅이 더 쉽다. 탐색 중 스택의 상태를 확인하거나, 현재 어떤 노드가 탐색되고 있는지 추적하는 것이 더 직관적이다.

단점

코드가 더 복잡해질 수 있음: 재귀 방식에 비해 코드가 조금 더 복잡해질 수 있다. 스택을 명시적으로 관리해야 하므로 반복문과 조건문이 추가되며, 탐색 과정에서 스택의 상태를 수동으로 처리해야 한다.
명시적인 스택 사용: 스택을 직접 구현하고 관리해야 하기 때문에, 기본적인 알고리즘을 처음 구현하는 경우에는 재귀 방식보다 덜 직관적일 수 있다.

3. 재귀 vs 스택 방식 요약

특징 재귀 방식 DFS 스택 방식 DFS

코드 간결성	매우 간결하고 직관적	다소 복잡할 수 있음
재귀 깊이 제한	재귀 깊이 제한에 걸릴 수 있음	제한이 없으며, 매우 깊은 탐색에 적합
메모리 사용	함수 호출 스택을 사용하여 자동 관리	스택을 명시적으로 관리 가능
디버깅 용이성	깊은 재귀 호출에서 디버깅이 어려울 수 있음	디버깅이 상대적으로 쉬움
성능	함수 호출 오버헤드가 발생할 수 있음	함수 호출 오버헤드가 없어 더 효율적
사용 사례	적당한 깊이의 그래프 탐색	매우 깊은 그래프나 트리 탐색에 적합

4. 언제 재귀 방식과 스택 방식을 선택할까?

재귀 방식:
- 그래프의 깊이가 깊지 않거나, 간단한 문제를 빠르게 해결해야 할 때 적합하다.
- 코드가 간결하고 구현이 쉬워 빠르게 알고리즘을 작성할 수 있다.
- 재귀 깊이 제한을 넘을 가능성이 없는 경우, 직관적인 구현이 가능하다.
스택 방식:
- 깊이가 매우 깊은 그래프를 탐색해야 하거나, 재귀 호출로 인해 스택 오버플로가 발생할 수 있는 경우에 적합하다.
- 메모리 사용을 명확하게 관리해야 하거나, 성능을 최적화해야 하는 상황에서 더 나은 선택일 수 있다.
- 디버깅이 중요한 경우, 스택을 명시적으로 사용하면 보다 직관적인 상태 추적이 가능하다.
재귀 방식의 DFS는 간결하고 직관적인 구현이 가능하지만, 재귀 깊이 제한이 있는 경우 문제가 발생할 수 있다.
스택 방식의 DFS는 깊이 제한 문제를 피할 수 있으며, 성능을 최적화할 수 있지만, 코드가 더 복잡해질 수 있다.

DFS의 특징

시간 복잡도:
- 그래프의 노드 수를 V, 간선 수를 E라고 할 때, DFS의 시간 복잡도는 O(V + E)이다.
  - 모든 노드를 한 번씩 방문하고, 모든 간선을 한 번씩 탐색하기 때문이다.
공간 복잡도:
- DFS는 재귀 호출을 사용할 경우, 재귀 호출 스택이 깊어질 수 있습니다. 최악의 경우 O(V)의 공간을 사용한다.
- 스택을 사용하는 경우에도 비슷하게 O(V)의 공간을 사용한다.
용도:
- 경로 찾기: DFS는 특정 노드에서 다른 노드로 가는 경로를 찾는 데 유용하다.
- 사이클 탐지: DFS는 그래프에서 사이클이 있는지 확인하는 데 자주 사용된다.
- 위상 정렬: 방향 그래프에서 위상 정렬을 수행할 때 DFS를 기반으로 할 수 있다.
- 연결 요소 탐색: DFS는 그래프의 모든 연결 요소를 탐색할 때 사용된다.
장점:
- 구현이 간단하고, 특정 경로 탐색이나 그래프의 모든 노드를 방문하는 데 효과적이다.
- 재귀와 스택을 사용한 두 가지 방식 모두 명확한 알고리즘 흐름을 제공한다.
단점:
- 재귀로 구현할 경우 재귀 깊이 제한에 걸릴 수 있다. 이 때문에 매우 깊은 그래프 탐색에서는 스택 기반 구현이 더 안전할 수 있다.
- DFS는 최단 경로를 보장하지 않는다. (최단 경로를 찾는 데는 너비 우선 탐색(BFS)을 사용해야 합니다.)

DFS는 그래프나 트리에서 깊이를 우선으로 탐색하는 알고리즘으로, 재귀나 스택을 통해 구현할 수 있다.
시간 복잡도는 O(V + E)로, 모든 노드와 간선을 한 번씩 방문한다.
DFS는 경로 탐색, 사이클 탐지, 연결 요소 찾기 등의 문제를 해결할 때 효과적으로 사용된다.

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms

728x90