DFS와 BFS 차이를 처음 배울 때는 깊이 우선, 너비 우선이라는 정의부터 외우게 됩니다. 그런데 문제를 풀기 시작하면 진짜 헷갈리는 지점은 정의가 아니라, 지금 어떤 탐색을 먼저 떠올려야 하느냐입니다.
실제로 중요한 건 이름보다 문제의 요구입니다. 최단 칸 수를 묻는지, 가능한 경우를 끝까지 펼쳐 봐야 하는지에 따라 DFS와 BFS의 선택이 갈립니다. 이번 글은 정의 비교가 아니라 문제 풀이 관점에서 둘을 정리합니다.
DFS와 BFS 선택 기준
- 최단 이동 횟수가 중요하면 BFS
- 가능한 경우를 끝까지 만들고 되돌아와야 하면 DFS
- 레벨 순서가 중요하면 BFS
- 구조 분석과 백트래킹이 중요하면 DFS
즉, DFS와 BFS는 누가 더 좋은 알고리즘이 아니라 문제에서 원하는 탐색 순서가 다른 도구입니다.
탐색 감각
BFS 감각
BFS는 시작점에서 가까운 곳부터 한 겹씩 넓게 퍼져 나갑니다. 그래서 queue가 잘 어울리고, 최소 이동 횟수나 같은 레벨 처리와 잘 맞습니다.
DFS 감각
DFS는 한 길을 끝까지 따라가다가 막히면 되돌아옵니다. 그래서 재귀나 stack이 잘 어울리고, 가능한 선택을 끝까지 만들어 보는 문제와 잘 맞습니다.
트리 문제
레벨 처리
트리의 레벨 순회, 같은 깊이 노드 묶기, 루트에서 가장 가까운 리프 찾기처럼 한 층씩 처리해야 하는 문제는 BFS가 더 자연스럽습니다.
서브트리 계산
서브트리 크기, 리프까지 내려가며 누적하기, 트리 DP처럼 자식 계산을 끝낸 뒤 부모를 처리해야 하는 문제는 DFS가 더 편합니다.
일반 그래프 문제
구조 분석
연결 요소, 도달 가능 여부, 사이클 탐지, 위상 정렬, SCC처럼 그래프 구조를 따라 깊게 분석해야 하는 문제는 DFS 계열이 자주 쓰입니다.
거리 확장
시작점에서 거리 1, 거리 2, 거리 3처럼 퍼져 나가는 해석이 중요하면 BFS가 더 직접적입니다. 친구 추천 단계, 바이러스 확산, 거리 k 정점 찾기 같은 문제가 그렇습니다.
최단 거리
문제에서 최소 이동 횟수, 가장 적은 간선 수, 몇 번 만에 도착 같은 표현이 보이면 BFS를 먼저 떠올리는 편이 안전합니다. 무가중치 그래프에서는 BFS가 먼저 도착한 순간의 거리가 곧 최단 거리이기 때문입니다.
from collections import deque
def shortest_steps(grid, start, goal):
n, m = len(grid), len(grid[0])
q = deque([(start[0], start[1], 0)])
visited = [[False] * m for _ in range(n)]
visited[start[0]][start[1]] = True
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while q:
x, y, dist = q.popleft()
if (x, y) == goal:
return dist
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 0 and not visited[nx][ny]:
visited[nx][ny] = True
q.append((nx, ny, dist + 1))
return -1무가중치 최단 거리라면 BFS를 먼저 떠올리는 습관이 가장 중요합니다.
완전 탐색
조합, 순열, 경로 수 세기, N-Queen처럼 가능한 경우를 끝까지 만들어 봐야 하는 문제는 DFS가 훨씬 자연스럽습니다. 현재 선택을 한 뒤 더 내려가 보고, 안 되면 취소하고, 다음 선택을 시도하는 흐름이 바로 DFS이기 때문입니다.
def count_paths(graph, current, target, visited):
if current == target:
return 1
total = 0
visited.add(current)
for nxt in graph[current]:
if nxt not in visited:
total += count_paths(graph, nxt, target, visited)
visited.remove(current)
return total이럴 때 BFS는 정답이 틀린 건 아니어도 문제의 본질과 조금 어긋납니다. 레벨 확장보다 분기 탐색과 되돌리기가 핵심이기 때문입니다.
메모리와 구현
둘 다 기본 순회 시간은 보통 O(V+E)로 설명합니다. 하지만 BFS는 같은 레벨 노드가 queue에 많이 쌓일 수 있고, DFS는 현재 경로 중심으로 stack이나 재귀가 쌓입니다. 그래서 그래프 모양에 따라 메모리 부담 양상이 달라집니다.
특히 파이썬에서 재귀 DFS를 쓸 때는 깊이가 깊으면 재귀 제한을 조심해야 합니다. 반대로 BFS는 폭이 넓은 그래프에서 queue 크기가 커질 수 있습니다.
문제 키워드
- BFS 힌트: 최소 이동 횟수, 최단 칸 수, 몇 단계 만에 도착, 시작점에서 거리 k, 레벨 순회, 동시에 퍼짐
- DFS 힌트: 가능한 경우 모두 탐색, 경로 하나를 끝까지 진행, 백트래킹, 사이클 탐지, 위상 정렬, 서브트리 계산
이 기준은 절대 규칙은 아니지만, 코딩테스트 입문 단계에서는 꽤 강한 힌트가 됩니다.
마무리
DFS와 BFS 차이를 한 문장으로 정리하면 이렇습니다. 가까운 것부터 넓게 확인해야 하면 BFS, 한 경로를 끝까지 밀어붙였다가 되돌아와야 하면 DFS입니다.
관련해서 기본 개념 자체를 다시 보고 싶다면 BFS 알고리즘 기초 글, DFS 알고리즘 기초 글, 기존 비교 글도 함께 보면 좋습니다. 외부 참고 자료로는 cp-algorithms BFS와 cp-algorithms DFS를 추천합니다.
