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

깊이 우선 탐색 DFS

"그래프 탐색 기법 중 하나로, 한 노드에서 출발하여 최대한 깊이 들어간 후 다시 돌아오는 방식"

• 재귀(Recursion) 또는 스택(Stack)으로 구현 가능
• 한 경로를 끝까지 탐색한 후, 다시 돌아가면서 다른 경로 탐색
• 트리, 그래프, 미로 탐색 등에서 많이 사용됨

---

DFS 동작 원리

1. 시작 노드에서 가능한 한 깊이 내려감
2. 더 이상 갈 곳이 없으면 되돌아옴 (Backtracking)
3. 모든 노드를 방문할 때까지 반복

출처: https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/

# Pseudo Code
FUNCTION DFS(node):
    방문[node] = True  # 현재 노드를 방문 처리
    출력(node)  # 노드 방문

    FOR 모든 인접 노드 in node의 이웃 리스트:
        IF 방문[인접 노드] == False THEN
            DFS(인접 노드)  # 재귀 호출
            
            
# 재귀 방식
def dfs(graph, node, visited):
    if visited[node]:  # 이미 방문한 노드라면 리턴
        return

    visited[node] = True  # 현재 노드 방문 처리
    print(node, end=' ')  # 방문한 노드 출력

    for neighbor in graph[node]:  # 인접 노드 탐색
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)  # 재귀 호출

# 그래프 (인접 리스트 표현)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}

visited = {key: False for key in graph}  # 방문 기록 초기화
dfs(graph, 1, visited)


# 스택 방식
def dfs_iterative(graph, start):
    stack = [start]  # 스택을 사용하여 DFS 구현
    visited = {key: False for key in graph}  # 방문 기록 초기화

    while stack:
        node = stack.pop()  # 스택에서 하나 꺼내기
        if not visited[node]:  # 방문하지 않았다면
            print(node, end=' ')  # 노드 출력
            visited[node] = True  # 방문 처리
            stack.extend(reversed(graph[node]))  # 인접 노드 추가 (순서를 유지하기 위해 reverse)

# 그래프 (인접 리스트 표현)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}

dfs_iterative(graph, 1)

---

DFS의 시간복잡도

경우	시간복잡도
그래프(V = 노드, E = 간선)	O(V + E)
트리(N = 노드 개수)	O(N)

 

✅ 모든 노드를 방문하므로 O(V + E) (그래프)
✅ 트리에서는 O(N), 연결 리스트에서는 O(N)

---

DFS의 장단점

장점

 

• 구현이 간단함 (재귀 or 스택 사용 가능)
• 백트래킹(Backtracking) 문제 해결에 적합
• 모든 경로를 탐색하는 문제에 유용 (예: 미로 찾기, 조합 생성)

단점

• 무한 루프 위험 (사이클이 있는 그래프에서 방문 체크를 안 하면 무한 탐색)
• 깊이가 너무 깊으면 스택 오버플로우 발생 가능 (재귀 호출이 많을 경우)

결론

DFS는 한 경로를 끝까지 탐색한 후 돌아오는 방식이며, 그래프 탐색, 백트래킹 문제 해결에 매우 유용하다.