DFS (Depth-First Search)

Jeonghwan Yoon·2025년 3월 30일

DFS란?

DFS는 그래프의 가장 깊은 정점까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아오는(Backtracking) 방식
스택(Stack) 또는 재귀(Recursive Function) 로 구현
보통 경로 기반의 완전탐색, 백트래킹, 사이클 탐지 등에 사용

언제 사용되는가?

목적	설명
모든 경로 탐색	깊이 기반 경로 탐색, 경우의 수 확인
백트래킹	조합, 순열 등 조건 분기 탐색
연결 요소 찾기	그래프에서 떨어진 컴포넌트 찾기
사이클 탐지	순환 경로 유무 판별
조합/순열 생성	DFS + 조건 분기로 구현 가능

동작 방식

시작 노드를 방문하고 처리
방문한 노드에서 인접한 노드로 이동
더 이상 방문할 곳이 없을 때까지 반복
더 이상 진행 불가하면 되돌아가서 다른 분기로 이동

구현 예시 (Python)

재귀 함수 방식

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

graph = [
    [],         # 0번 노드 미사용
    [2, 3],     # 1번 → 2, 3
    [4],
    [4],
    [],
]
visited = [False] * 5
dfs(graph, 1, visited)  # 출력: 1 2 4 3

스택 기반 반복문 방식 (재귀 없이)

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]))  # 순서 보장

시간 복잡도

항목	시간 복잡도
전체 탐색	O(N + M) (N: 노드 수, M: 간선 수)

실전 문제 유형

문제 유형	설명
섬의 개수	DFS로 연결된 영역 탐색
조합, 순열	DFS + visited 배열로 구현
미로 경로 찾기	한 갈래씩 끝까지 가며 경로 탐색
백트래킹	조건 분기 + 되돌아가기
사이클 탐지	방문 중인 노드가 또 나오면 순환 존재

Python vs C 구현 차이

항목	Python	C
재귀	자유롭게 사용	스택 오버플로우 주의
스택	리스트로 사용 가능	배열 + top 포인터 직접 구현
인접 리스트	리스트 배열	포인터 배열 또는 연결 리스트
visited 배열	bool 리스트	bool visited[] 선언

연관 개념

개념	설명
Stack	DFS 내부 동작의 원리
백트래킹	DFS 기반 조합/경로 탐색 알고리즘
visited 배열	중복 방문 방지 필수
순열/조합 생성	DFS + 조건 분기로 구현