1. DFS란 무엇인가?
DFS(Depth-First Search, 깊이 우선 탐색)는 한 경로를 끝까지 파고든 뒤 막히면 되돌아와(backtracking) 다른 경로를 탐색하는 방법
- Level(깊이): 재귀 호출이 누적된 단계(=현재 경로 길이)
- Branch(가지): 현재 상태에서 선택 가능한 다음 후보들의 집합
DFS는 보통 재귀(함수 호출 스택 = 탐색 깊이)로 구현하고, 백트래킹(불필요한 가지를 조기에 자름) 전략과 자주 사용
2-1. BFS vs DFS
| 구분 | BFS | DFS |
|---|---|---|
| 탐색 방식 | 가까운 노드부터(Level by Level) | 깊게 파고듦, 막히면 백트래킹 |
| 자료구조 | 큐(Queue, FIFO) | 스택(Stack, LIFO) / 재귀 |
| 대표 활용 | 최단 거리, 레벨 탐색 | 경로 탐색, 완전 탐색, 백트래킹 |
| 시간 복잡도 | O(V+E) | O(V+E) (같음) |
| 메모리 | 큐 크기 = 레벨당 노드 수 | 재귀 깊이(스택) |
| 예시 문제 | 미로 탐색(2178) | N과 M 시리즈, 연결 요소 |
2-2) 재귀 vs DFS vs 백트래킹 (혼동 금지 표)
| 구분 | 핵심 정의 | 목적/용도 | 구현 특징 | 예시 |
|---|---|---|---|---|
| 재귀(Recursion) | 자기 자신을 호출 | 구조적/반복적 정의 문제 표현 | 호출 스택 사용, Base/Recursive case 필요 | 팩토리얼, 하노이탑 |
| DFS | 깊이 우선 그래프/상태 탐색 | 연결성/경로/완전탐색 | 재귀 또는 명시적 스택 | 연결 요소, 경로 찾기 |
| 백트래킹 | DFS 중 가지치기 전략 | 경우의 수 탐색 최적화 | 불만족 분기 조기 중단 | N과 M, N-Queens |
요약: DFS=탐색 방식, 백트래킹=DFS 중 전략, 재귀=구현 도구
3. DFS 기본 뼈대
수도코드
DFS(u):
visited[u] ← true
for v in neighbors(u):
if not visited[v]:
DFS(v)파이썬
# 인접 리스트 그래프 예시
graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1],
4: [2],
5: [2],
}
visited = set()
def dfs(u, level=0):
indent = " " * level
print(f"{indent}visit {u} (level={level})")
visited.add(u)
# branch: u와 인접한 모든 정점으로 분기
for v in graph[u]:
if v not in visited:
dfs(v, level + 1)
dfs(1)4. DFS + 델타(격자) 탐색 스니펫
# 격자 DFS 기본 패턴
dy, dx = (-1, 1, 0, 0), (0, 0, -1, 1)
def dfs_grid(y, x):
visited[y][x] = True
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if 0 <= ny < N and 0 <= nx < M and not visited[ny][nx]:
if board[ny][nx] == 1:
dfs_grid(ny, nx)5. DFS + 백트래킹: N과 M 시리즈(순열/조합/중복)
핵심 포인트:
- Level = 현재 뽑은 원소 개수
- Branch = 이번 단계에서 선택 가능한 숫자들
- Backtracking = 호출 복귀 시 상태(배열, 사용표시) 원복
(1) 순열(중복X) — 15649
N, M = map(int, input().split())
used = [False] * (N + 1)
pick = []
def dfs():
if len(pick) == M:
print(*pick)
return
for x in range(1, N + 1): # branch
if not used[x]:
used[x] = True # 상태 변화
pick.append(x)
dfs() # level+1
pick.pop() # backtrack
used[x] = False # 상태 원복
dfs()(2) 조합(중복X, 오름차순) — 15650
N, M = map(int, input().split())
pick = []
def dfs(start):
if len(pick) == M:
print(*pick)
return
for x in range(start, N + 1):
pick.append(x)
dfs(x + 1) # 다음은 더 큰 수만
pick.pop()
dfs(1)(3) 중복 순열 — 15651
N, M = map(int, input().split())
pick = []
def dfs():
if len(pick) == M:
print(*pick)
return
for x in range(1, N + 1): # 중복 허용 → used 불필요
pick.append(x)
dfs()
pick.pop()
dfs()(4) 중복 조합(오름차순) — 15652
N, M = map(int, input().split())
pick = []
def dfs(start):
if len(pick) == M:
print(*pick)
return
for x in range(start, N + 1): # 자기 자신 재선택 허용
pick.append(x)
dfs(x) # start 유지
pick.pop()
dfs(1)6. 예시 문제 풀이
[백준 11724] 연결 요소의 개수 (실버2)
문제 요약
- 정점 개수 , 간선 개수
- 무방향 그래프에서 연결 요소의 개수 출력
접근
- 인접 리스트 구성 → 방문하지 않은 정점에서 DFS 1회 = 연결 요소 1개
- 모든 정점을 훑으며 방문 안 된 정점 발견 → DFS 호출 & 카운트
코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
adj[a].append(b)
adj[b].append(a) # 무방향
visited = [False] * (N + 1)
def dfs(u):
visited[u] = True
for v in adj[u]: # branch: 인접 정점들
if not visited[v]:
dfs(v) # level+1
components = 0
for node in range(1, N + 1):
if not visited[node]: # 아직 방문 안 했다면 새로운 컴포넌트 시작
dfs(node)
components += 1
print(components)7. 헷갈리는 포인트
❌ 오개념 1: DFS와 재귀는 같은건가?
- 재귀는 구현법일 뿐, 스택으로도 구현 가능
❌ 오개념 2: 백트래킹이랑 DFS는 같은건가?
- 백트래킹은 DFS 중 “가지치기” 전략
❌ 오개념 3: 방문 체크 시점은 언제 해야되는건가?
- DFS는 진입 즉시 방문 체크(중복 호출/사이클 방지)
❌ 오개념 4: 아무거나 먼저 방문해도 되나? 정렬 여부는?
- 정점 방문 순서를 특정하려면 인접 목록 정렬이 필요할 수 있음
❌ 오개념 5: 상태 원복은 언제 해야되나?
- 순열/조합류에선
append/pop,used True/False가 핵심
8. DFS 심화 응용 (문제 가이드 + 링크)
-
백준 10026번 적록색약
→ DFS + 델타 탐색 응용
→ 일반 모드와 색약 모드에서 각각 영역을 세야 하므로, DFS 조건 분기가 필요 -
백준 1987번 알파벳
→ DFS + 백트래킹
→ 같은 알파벳은 재방문 불가 →used set또는 비트마스크로 상태 관리. 경로 최대 길이 찾기 문제 -
백준 9466번 텀 프로젝트
→ DFS + 사이클 탐지
→ 방향 그래프에서 사이클에 포함되는 정점 개수를 찾는 문제. DFS 중 방문/완료 상태 구분 필요 -
백준 1520번 내리막길
→ DFS + DP (메모이제이션)
→ DFS로 경로 탐색하면서, 중복 경로는 DP로 캐싱해야 시간 안에 해결 가능 -
백준 11724번 연결 요소의 개수
→ DFS 그래프 탐색 기본기
→ 방문하지 않은 정점마다 DFS 1회 = 연결 요소 1개. DFS 입문 필수 문제
