anonymous.rs

알고리즘: 깊이 우선 탐색 (DFS, Depth-First Search)

8 min read

깊이 우선 탐색 (DFS, Depth-First Search) 완벽 가이드

BFS(너비 우선 탐색)와 쌍벽을 이루는 그래프 탐색 알고리즘, **깊이 우선 탐색(DFS)**에 대해 알아보겠습니다. 한 우물을 끝까지 파고드는 성질 덕분에 백트래킹(Backtracking)이나 완전 탐색 문제에서 자주 사용됩니다.

1. DFS란?

DFS는 시작 정점(Node)에서 출발하여 특정 경로를 따라 갈 수 있는 한 가장 깊게(끝까지) 탐색한 후, 더 이상 갈 곳이 없으면 이전의 갈림길로 되돌아가서 다른 경로를 탐색하는 알고리즘입니다.

미로를 탐색할 때 한쪽 벽만 짚고 끝까지 갔다가, 막다른 길을 만나면 갈림길로 돌아와 다른 길을 찾는 방식과 완벽히 동일합니다.

2. 동작 과정과 스택/재귀

DFS 알고리즘은 나중에 들어온 갈림길(최근 상태)로 되돌아가야 하므로 LIFO(Last-In, First-Out) 특성을 가진 스택(Stack) 자료구조를 사용하거나, 함수의 호출 스택을 이용하는 **재귀(Recursion)**로 구현합니다. (실무와 코딩 테스트에서는 코드가 간결한 재귀 방식을 압도적으로 많이 사용합니다.)

  1. 현재 정점 방문: 현재 정점을 방문 처리합니다.
  2. 인접 정점 탐색: 현재 정점과 연결된 인접 정점들을 하나씩 확인합니다.
  3. 깊이 진입 (재귀): 방문하지 않은 인접 정점이 있다면, 그 정점을 새로운 시작점으로 삼아 DFS 함수를 재귀적으로 호출하여 더 깊이 들어갑니다.
  4. 백트래킹 (되돌아가기): 모든 인접 정점을 방문했거나 길이 막혔다면, 재귀 호출이 종료되면서 이전 정점(부모 정점)으로 자연스럽게 되돌아갑니다.

3. 파이썬(Python) 구현 예시

재귀 함수를 이용한 DFS 구현이 가장 직관적이고 널리 쓰입니다.

재귀(Recursion)를 이용한 DFS

def dfs_recursive(graph, current_node, visited):
    # 현재 노드를 방문 처리
    visited.append(current_node)
    print(f"방문: {current_node}")
    
    # 현재 노드와 연결된 다른 노드들을 재귀적으로 방문
    for neighbor in graph[current_node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
            
    return visited
 
# 그래프 인접 리스트 예시
graph = {
    1: [2, 3, 8],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [2],
    5: [2],
    6: [3],
    7: [3],
    8: [1]
}
 
print("DFS 재귀 탐색 순서:")
visited_nodes = []
dfs_recursive(graph, 1, visited_nodes)
# 예상 출력: 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 -> 8
# (1에서 2로 들어간 후, 2의 자식인 4, 5를 끝까지 탐색하고 나서야 3으로 넘어감)

스택(Stack)을 이용한 DFS (반복문)

재귀 깊이 제한(RecursionError)이 걱정되거나 명시적인 자료구조를 써야 할 때는 리스트를 스택으로 사용합니다.

def dfs_stack(graph, start_node):
    visited = []
    stack = [start_node]
    
    while stack:
        # 스택의 맨 위(마지막에 넣은) 노드를 꺼냄
        current = stack.pop()
        
        if current not in visited:
            visited.append(current)
            
            # 스택은 LIFO 구조이므로, 인접 노드를 역순으로 넣어야 
            # 번호가 작은 노드부터 먼저 탐색하게 됨 (선택 사항)
            for neighbor in reversed(graph[current]):
                if neighbor not in visited:
                    stack.append(neighbor)
                    
    return visited

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

정점(Vertex)의 수를 , 간선(Edge)의 수를 라고 할 때 (BFS와 동일):

  • 시간 복잡도: (인접 리스트 기준)
    • 모든 정점을 한 번씩 방문하고, 각 정점에서 나가는 간선들을 한 번씩만 확인하므로 그래프 전체를 탐색하는 데 가 소요됩니다.
  • 공간 복잡도:
    • 방문 배열(Visited)을 위한 공간 가 필요합니다.
    • 스택 메모리 또는 재귀 호출 스택(Call Stack)의 깊이가 최악의 경우(그래프가 일직선인 경우) 정점의 개수 만큼 깊어질 수 있으므로 가 필요합니다.

5. DFS의 핵심 활용 사례

DFS는 깊이를 끝까지 파고드는 특성 덕분에 다음과 같은 유형에서 강력합니다.

  1. 경로의 특징을 저장/유지해야 할 때: 목적지까지 가는 경로 상에 특정 조건(예: 동일한 숫자는 밟으면 안 됨)이 있거나, 경로 자체를 기억해야 할 때는 BFS보다 DFS가 적합합니다. (BFS는 여러 경로를 동시에 진행하므로 각 경로의 특징을 독립적으로 저장하기 까다롭습니다.)
  2. 모든 경우의 수를 찾는 완전 탐색 (백트래킹, Backtracking): N-Queen 문제, 스도쿠, 가능한 모든 조합/순열 찾기 등 어떤 결정을 내리고 끝까지 가본 후, 아니면 되돌아와서 다른 결정을 내리는 유형에서 필수적입니다.
  3. 사이클(Cycle) 검출: 방향 그래프에서 현재 탐색 중인 경로(재귀 스택) 상의 노드를 다시 방문하게 된다면 사이클이 존재함을 쉽게 알 수 있습니다.

요약

DFS(깊이 우선 탐색)는 재귀 함수를 이용하여 한 갈래의 길을 끝까지 탐색하고 되돌아오는 우직한 탐색 알고리즘입니다. 의 빠른 속도로 그래프의 모든 노드를 순회할 수 있으며, 특히 경로의 특징을 유지하며 모든 경우의 수를 탐색하는 백트래킹(Backtracking) 알고리즘의 뼈대가 되므로 템플릿처럼 코드를 손에 익혀두어야 합니다.

Graph View