DFS 깊이 우선 탐색의 원리와 활용

DFS란?

Depth-First Search (DFS)는 그래프나 트리에서 
한 방향으로 끝까지 파고들었다가, 갈 곳이 없으면 되돌아오는 탐색 알고리즘입니다.

 

즉, 가장 깊은 노드부터 먼저 탐색

---

DFS가 왜 중요한가?

• 트리 구조 분석
• 백트래킹 문저 (ex: N-Queen, 조합 탐색)
• 경로 찾기 (모든 가능한 경로를 보고 싶을 때)
• 싸이클 탐지

---

DFS 두가지 구현 

1) 재귀 (가장 직관적)

def dfs_recursive(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs_recursive(graph, neighbor, visited)

2) 스택 (명시적 구현)

def dfs_stack(graph, start):
    visited = [False] * len(graph)
    stack = [start]

    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(v, end=' ')
            stack.extend(reversed(graph[v]))

---

DFS 동작 순서 예시 (재귀)

그래프:

graph = {
    1: [2, 3],
    2: [4, 5],
    3: [],
    4: [],
    5: []
}

visited = [False] * 6
dfs_recursive(graph, 1, visited)

# 1 2 4 5 3

깊이 우선 → 1 → 2 → 4 → 5 → 3

---

DFS 실전 활용 예시

백트래킹 (조합/순열 찾기)

def backtrack(path, nums):
    if not nums:
        print(path)
        return
    for i in range(len(nums)):
        backtrack(path + [nums[i]], nums[:i] + nums[i+1:])

싸이클 탐지

def has_cycle(graph, v, visited, parent):
    visited[v] = True
    for neighbor in graph[v]:
        if not visited[neighbor]:
            if has_cycle(graph, neighbor, visited, v):
                return True
        elif neighbor != parent:
            return True
    return False

---

DFS 시간 복잡도

• 시간복잡도: O(V + E)
  (V: 노드 수, E: 간선 수)
• 공간복잡도: O(V) + 재귀 깊이

---

상황 별 정리

상황	DFS 활용 이유
가능한 모든 경우의 수 탐색	백트래킹 기반
트리 구조 순회	DFS가 자연스럽게 사용됨
재귀 함수로 직관적 구현	파이썬에 적합
방문 순서보다 경로에 집중	DFS가 더 적합

---

정리

항목	설명
이름	DFS (Depth-First Search)
탐색 방식	깊게 들어간 후 되돌아오기
자료구좋	스택 (또는 재귀)
시간복잡도	O(V + E)
주요 활용	백트래킹, 경로 찾기, 싸이클 탐지 등