깊이 우선 탐색(DFS) 쉽게 이해하기: 동작 원리, 코드, 시간 복잡도

DFS가 해결하는 문제

DFS는 한 가지를 끝까지 탐색한 다음 다음 가지로 넘어가는 방식으로 "여기서 어디까지 갈 수 있는가?"에 답합니다. 경로의 길이보다 구조가 중요할 때 유용합니다. 미로에서 출구 찾기, 그래프에 사이클이 있는지 확인하기, 서로 의존하는 작업의 순서 정하기, 퍼즐의 모든 해 나열하기가 그 예입니다.

너비 우선 탐색과 달리 DFS는 최단 경로를 찾지 못합니다. 대신 현재 경로만 메모리에 유지하면 되고, 노드에 들어간 시점과 끝난 시점을 자연스럽게 기록할 수 있다는 것이 강점입니다.

핵심 아이디어

1. 현재 노드를 방문 처리합니다.
2. 방문하지 않은 이웃마다 그 노드로 이동해 거기서 1번을 반복합니다.
3. 방문하지 않은 이웃이 더 없으면 그 노드는 끝난 것입니다. 왔던 노드로 돌아갑니다.
4. 시작 노드로 돌아왔는데 방문하지 않은 이웃이 없으면 탐색이 끝납니다.

이전 노드로 돌아가는 것을 백트래킹이라고 합니다. 재귀를 쓰면 호출 스택이 이 일을 대신해 줍니다.

단계별 예제

BFS 글과 같은 무방향 그래프를 사용합니다. A–B, A–C, B–D, C–D, C–E, D–F. A에서 시작하고 이웃은 알파벳 순서로 시도합니다.

방문 순서는 A, B, D, C, E, F이고 종료 순서는 E, C, F, D, B, A입니다. 위상 정렬과 강연결 요소 알고리즘이 사용하는 것은 이 종료 순서입니다.

파이썬 구현

재귀 버전이 가장 짧고 아이디어에 가장 가깝습니다.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

리스트를 쓰면 예제는 읽기 쉽지만 in 검사가 O(n)이 됩니다. 큰 그래프에서는 멤버십 확인용으로 별도의 set을 두세요. 반복 버전은 명시적 스택을 사용해 파이썬의 재귀 한도를 피합니다. 원래 순서대로 꺼내지도록 이웃을 역순으로 넣습니다.

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in visited:
                stack.append(nxt)
    return order
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

BFS와 다른 점에 주목하세요. 여기서는 노드를 꺼낼 때 방문 처리하므로 한 노드가 스택에 여러 번 있을 수 있습니다. DFS에서는 이것이 올바르며 진짜 깊이 우선 순서를 유지해 줍니다.

방향 그래프에서 사이클 탐지

대표적인 DFS 응용은 각 노드에 색을 칠하는 것입니다. 흰색(아직 못 봄), 회색(현재 경로 위), 검은색(종료)으로 나눕니다. 회색 노드에 도달했다면 현재 경로로 되돌아오는 간선이 있다는 뜻이고, 이는 사이클입니다.

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    def visit(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True              # back edge
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[node] = BLACK
        return False
    return any(color[n] == WHITE and visit(n) for n in graph)
print(has_cycle({"a": ["b"], "b": ["c"], "c": ["a"]}))  # True
print(has_cycle({"a": ["b"], "b": ["c"], "c": []}))     # False

시간 복잡도와 공간 복잡도

변형과 흔한 실수

• 전위 순회와 후위 순회: 노드에 들어갈 때 기록하면 전위, 끝날 때 기록하면 후위입니다. 방향 비순환 그래프의 역후위 순서가 위상 정렬 순서입니다.
• 연결 요소: 아직 방문하지 않은 노드마다 새 DFS를 시작합니다. 시작할 때마다 하나의 연결 요소가 나옵니다.
• 반복 깊이 증가 DFS: 깊이 제한을 0, 1, 2, …로 늘려 가며 DFS를 실행합니다. BFS처럼 최단 경로를 찾으면서 DFS처럼 메모리를 적게 씁니다.
• 격자 위의 플러드 필(그림판의 페인트 통 도구)은 같은 색의 이웃한 칸에 대한 DFS 또는 BFS입니다.

그 밖의 흔한 버그: 방문 집합을 빼먹기(사이클이 있으면 무한 루프), visited=[] 같은 가변 기본 인자 사용하기(호출 간에 공유됨), 무방향 간선에서 부모로 되돌아가는 간선을 사이클로 착각하기.

DFS를 쓰는 경우와 실제 활용

• 도달 가능성 확인, 사이클 탐지, 위상 정렬, 연결 요소와 강연결 요소, 브리지와 단절점, 백트래킹을 이용한 완전 탐색에 DFS를 사용합니다.
• 최소 단계 수가 필요하면 BFS를, 간선에 가중치가 있으면 다익스트라나 A*를 대신 사용하세요.
• 코딩 인터뷰 문제: 섬의 개수, 그래프 복제, 수강 신청 순서(사이클 탐지), 이진 트리의 경로 합, 순열 생성.
• 실제 사례: 의존성 순서를 해결하는 빌드 시스템과 패키지 관리자, 제어 흐름을 분석하는 컴파일러, 미로 생성, 파일 시스템이나 HTML 문서의 트리 순회.