CS학습2026년 8월 25일

DFS: 스택 기반 후입선출(LIFO)로 깊이부터 파고드는 그래프 탐색

DFS(깊이 우선 탐색, Depth-First Search)는 시작 노드에서 갈 수 있는 한 끝까지 파고든 뒤 되돌아오며 탐색하는 그래프 순회 알고리즘이다. 재귀 호출 스택 또는 명시적 스택 자료구조를 이용해 구현하며, 백트래킹(backtracking)과 위상 정렬(topological sort), 사이클 탐지 같은 문제의 기반이 된다. BFS와 달리 최단

송민성5분 읽기

1. 개념

DFS(깊이 우선 탐색, Depth-First Search)는 그래프나 트리에서 한 방향으로 갈 수 있는 만큼 깊이 들어간 뒤, 더 갈 곳이 없으면 이전 분기점으로 돌아와(백트래킹) 다른 방향을 탐색하는 순회 알고리즘이다.

핵심은 "옆으로 넓게"가 아니라 "끝까지 깊게" 파고드는 방식이라는 점이다. 이 특성 때문에 후입선출(LIFO, Last-In-First-Out) 구조인 스택(stack)과 자연스럽게 맞아떨어진다. 재귀 함수를 쓰면 함수 호출 스택이 이 역할을 대신하고, 반복문으로 구현하면 명시적인 스택 자료구조를 사용한다.

2. 왜 사용하는가

전체 경로/조합 탐색: 백트래킹 기반 문제(순열, 조합, N-Queen 등)는 모든 가능성을 깊이 파고들며 검사해야 하므로 DFS가 자연스럽다.
연결 요소(connected component) 찾기: 그래프에서 서로 연결된 노드 그룹을 찾을 때 방문 순서가 중요하지 않으므로 DFS로 충분하다.
사이클 탐지: 방향 그래프에서 사이클이 있는지 확인할 때 DFS의 방문 상태(흰색/회색/검은색)를 활용한다.
위상 정렬(topological sort): 작업 순서 의존성을 정렬할 때 DFS의 후위 순회(post-order) 결과를 역순으로 사용한다.
메모리 효율: BFS는 같은 레벨의 노드를 모두 큐에 저장해야 하므로 넓고 얕은 그래프에서 메모리를 많이 쓴다. DFS는 현재 경로만 스택에 유지하므로 깊고 좁은 그래프에서 메모리 사용량이 적다.

3. 동작 원리

시작 노드를 방문 처리하고 스택(또는 재귀 호출)에 넣는다.
현재 노드의 인접 노드 중 방문하지 않은 노드를 하나 선택해 그 노드로 이동한다.
더 갈 수 있는 인접 노드가 없으면 스택에서 하나를 꺼내(pop) 이전 노드로 되돌아간다.
모든 노드를 방문할 때까지 2~3을 반복한다.

방문 여부를 기록하는 visited 집합이 없으면 순환 그래프에서 무한 루프에 빠지므로 반드시 필요하다.

4. 코드 예제

재귀 방식 (그래프 인접 리스트)

python

from typing import Dict, List, Set

def dfs_recursive(
    graph: Dict[str, List[str]],
    node: str,
    visited: Set[str] = None,
    order: List[str] = None,
) -> List[str]:
    if visited is None:
        visited = set()
        order = []

    visited.add(node)
    order.append(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)

    return order


graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": ["E"],
    "E": [],
}

print(dfs_recursive(graph, "A"))  # ['A', 'B', 'D', 'E', 'C']

반복 방식 (명시적 스택)

python

from typing import Dict, List

def dfs_iterative(graph: Dict[str, List[str]], start: str) -> List[str]:
    visited = {start}
    stack = [start]
    order = []

    while stack:
        node = stack.pop()  # 스택의 맨 위(가장 최근에 넣은 노드) 꺼내기
        order.append(node)

        # 방문 순서를 재귀와 동일하게 맞추려면 역순으로 push
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

    return order


print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'E', 'C']

응용: 방향 그래프 사이클 탐지

python

from typing import Dict, List

def has_cycle(graph: Dict[str, List[str]]) -> bool:
    # 0: 미방문, 1: 탐색 중(스택에 있음), 2: 탐색 완료
    state = {node: 0 for node in graph}

    def visit(node: str) -> bool:
        state[node] = 1
        for neighbor in graph[node]:
            if state[neighbor] == 1:
                return True  # 탐색 중인 노드를 다시 만남 -> 사이클
            if state[neighbor] == 0 and visit(neighbor):
                return True
        state[node] = 2
        return False

    return any(visit(node) for node in graph if state[node] == 0)


cyclic_graph = {"A": ["B"], "B": ["C"], "C": ["A"]}
acyclic_graph = {"A": ["B"], "B": ["C"], "C": []}

print(has_cycle(cyclic_graph))   # True
print(has_cycle(acyclic_graph))  # False

5. 시간 복잡도 또는 성능 특성

시간 복잡도: O(V + E) — V는 노드 수, E는 엣지 수. 모든 노드를 한 번씩 방문하고 각 엣지를 한 번씩 검사하기 때문이다.
공간 복잡도: O(V) — visited 집합과 스택(또는 재귀 호출 스택) 크기가 최악의 경우 노드 수만큼 커진다.
재귀 깊이 제한: 재귀 방식은 그래프가 깊으면 파이썬 기본 재귀 한도(약 1000)를 초과해 RecursionError가 발생할 수 있다. 이런 경우 반복 방식(명시적 스택)을 써야 한다.

python

import sys
print(sys.getrecursionlimit())  # 기본값 1000

6. 실무 사용 사례

파일 시스템 순회: 디렉터리 구조를 재귀적으로 탐색해 모든 하위 파일을 나열하는 로직(os.walk 내부도 유사한 원리).
의존성 그래프 해석: 패키지 매니저(npm, pip)가 패키지 간 의존성을 해석할 때 위상 정렬 기반으로 설치 순서를 결정한다.
컴파일러의 심볼 참조 분석: 변수/함수 참조 관계를 그래프로 만들어 순환 참조를 탐지한다.
웹 크롤러: 링크를 따라 깊이 우선으로 페이지를 탐색할 때(단, 실무에서는 무한 깊이 방지를 위해 깊이 제한을 둔다).
게임 AI의 미로 탐색, 퍼즐 풀이: 백트래킹으로 전체 해 공간을 탐색해야 하는 경우.

7. 주의할 점

무한 루프 방지: visited 처리를 빠뜨리면 순환 그래프에서 무한히 재귀/반복한다. 방문 표시는 노드를 스택에 넣는 시점에 하는 것이 안전하다(꺼낼 때 표시하면 중복 push가 발생할 수 있다).
최단 경로 보장 안 됨: DFS는 목표 노드를 찾더라도 그 경로가 최단 경로라는 보장이 없다. 최단 경로가 필요하면 BFS나 다익스트라(Dijkstra) 알고리즘을 써야 한다.
재귀 깊이 초과: 노드 수가 수만 개 이상인 깊은 그래프에서는 재귀 대신 반복(명시적 스택) 구현을 쓰거나 sys.setrecursionlimit을 조정해야 한다(단, 너무 늘리면 스택 오버플로로 프로세스가 죽을 수 있다).
양방향 그래프의 부모 노드 재방문: 무방향 그래프에서는 인접 노드에 자신을 가리키는 부모 노드가 포함되므로, 단순히 visited만 검사하면 문제없지만 엣지 정보를 추적할 때는 부모 노드를 별도로 제외해야 한다.

8. 핵심 정리

DFS는 스택(재귀 또는 명시적)을 이용해 한 경로를 끝까지 파고든 뒤 되돌아오는 탐색 방식이며, 시간 복잡도는 O(V + E), 공간 복잡도는 O(V)다. 최단 경로 탐색에는 적합하지 않지만 백트래킹, 사이클 탐지, 위상 정렬, 연결 요소 찾기처럼 "모든 경로를 파고들어야 하는" 문제에 강하다. 실무에서는 깊은 그래프에서 재귀 깊이 제한 문제를 피하기 위해 반복 방식 구현을 함께 알아두는 것이 안전하다.