DFS(깊이 우선 탐색) 파이썬 구현

DFS(Depth-First Search, 깊이 우선 탐색)는 트리나 그래프에서 한 우물을 끝까지 파고든 뒤, 길이 없으면 다시 돌아와서(백트래킹) 다른 길을 찾는 방식의 알고리즘입니다.

너비(층별)를 우선시하는 BFS가 큐(Queue)를 썼다면, DFS는 스택(Stack) 자료구조나 재귀함수(Recursion)를 사용하여 구현합니다. 코딩 테스트에서는 코드가 간결하고 직관적인 재귀함수 방식을 압도적으로 많이 사용합니다.

1. DFS의 핵심 작동 원리

현재 노드를 방문 처리(Visited)합니다.
현재 노드와 연결된 인접 노드들을 하나씩 확인합니다.
인접 노드 중에서 아직 방문하지 않은 노드가 있다면, 그 노드를 시작점으로 삼아 자기 자신(DFS 함수)을 다시 호출(재귀)합니다.
더 이상 방문할 연결 노드가 없으면, 이전 노드로 돌아가서(백트래킹) 다른 노드를 탐색합니다.

2. 파이썬 DFS 템플릿 코드 (재귀함수)

앞서 BFS에서 보았던 것과 동일한 1차원 그래프를 DFS로 탐색하는 기본 코드입니다. 재귀함수를 쓰기 때문에 코드가 아주 짧습니다.

python# 1. 맵 정보 (각 노드가 연결된 정보)
graph = [
    [],        # 0번 노드는 비워둠
    [2, 3, 8], # 1번 노드
    [1, 7],    # 2번 노드
    [1, 4, 5], # 3번 노드
    [3, 5],    # 4번 노드
    [3, 4],    # 5번 노드
    [7],       # 6번 노드
    [2, 6, 8], # 7번 노드
    [1, 7]     # 8번 노드
]

visited = [False] * 9  # 2. 방문 여부를 체크할 리스트
 
def dfs(v):  # 3. DFS 함수 정의
   
    visited[v] = True # 현재 노드를 방문 처리하고 출력
    print(v, end=' ')    
   
    for i in graph[v]:  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        if not visited[i]: # 방문하지 않은 노드라면
            dfs(i)         # 깊이 파고들기(재귀 호출)

dfs(1) # 1번 노드부터 탐색 시작

Output

1 2 7 6 8 3 4 5

💡 BFS와 DFS의 출력 결과 차이점

동일한 그래프지만 탐색 순서가 다릅니다.
BFS(너비): 1 -> (2, 3, 8) 방문 후 그다음 층 방문.
DFS(깊이): 1 -> 2로 간 뒤, 2와 연결된 7, 7과 연결된 6... 식으로 가장 끝까지 파고듭니다.

3. 실전 팁: 언제 DFS를 써야 할까?

코딩 테스트에서 다음과 같은 문제가 나오면 무조건 DFS(특히 백트래킹)를 떠올리시면 됩니다.

모든 경우의 수를 다 찾아야 할 때 (순열, 조합 등)
조건에 맞는 경로의 개수를 찾을 때 (A에서 B로 가는 모든 경로)
연결된 덩어리의 개수(Connected Component)를 셀 때 (섬의 개수, 바이러스 전파 등 - 이 경우 BFS도 가능하지만 코드가 짧은 DFS를 많이 씁니다).

🚨 주의사항: 파이썬 재귀 제한 설정

파이썬은 기본적으로 재귀 호출 깊이를 1,000번 정도로 제한하고 있습니다. 백준 같은 곳에서 DFS 문제를 풀 때는 가장 상단에 아래 코드를 반드시 적어주어야 RecursionError를 막을 수 있습니다.

pythonimport sys
sys.setrecursionlimit(10**6) # 재귀 깊이 제한을 100만으로 늘려줌