DFS와 백트래킹 차이는 코딩테스트를 하다 보면 아주 자주 헷갈립니다. 둘 다 재귀로 구현되는 경우가 많고, 깊게 들어갔다가 다시 돌아온다는 느낌도 비슷하기 때문입니다. 하지만 둘은 완전히 같은 말이 아닙니다.
이번 글에서는 DFS를 탐색 방식으로, 백트래킹을 불필요한 가지를 미리 잘라내며 정답 후보를 찾는 전략으로 구분해서 설명하겠습니다. 그리고 단순 재귀 모양이 비슷하다고 같은 개념으로 뭉뚱그리면 왜 실전 문제에서 자꾸 헷갈리는지도 함께 정리하겠습니다.
DFS는 무엇이고 백트래킹은 무엇일까
DFS는 말 그대로 깊이 우선 탐색입니다. 한 갈래를 가능한 만큼 끝까지 들어가 본 뒤, 더 갈 곳이 없으면 다시 돌아옵니다. 반면 백트래킹은 이 탐색 흐름 위에서 “이 갈래는 더 봐도 정답이 안 되겠다”라고 판단되는 순간 더 깊이 들어가지 않고 잘라내는 전략입니다.
- DFS: 탐색 순서와 이동 방식에 대한 말
- 백트래킹: 정답이 아닌 갈래를 일찍 버리는 전략에 대한 말
왜 둘을 같은 말처럼 느끼게 될까
실제로 많은 백트래킹 문제를 DFS 재귀 구조로 구현하기 때문입니다. 그래서 코드 모양은 비슷해도, 핵심 질문은 다릅니다. DFS에서는 어디까지 방문할지를 보고, 백트래킹에서는 이 경로를 더 볼 가치가 있는지를 봅니다.
def dfs(node):
visited[node] = True
for nxt in graph[node]:
if not visited[nxt]:
dfs(nxt)
def backtrack(path):
if is_invalid(path):
return
if is_answer(path):
result.append(path[:])
return
for candidate in candidates:
path.append(candidate)
backtrack(path)
path.pop()DFS 개념 참고를 보면 깊이 우선 탐색이라는 이름 자체는 단순하지만, 코딩테스트에서는 그 위에 가지치기 전략이 붙으면서 백트래킹과 구분이 필요해집니다.
위 예시처럼 DFS는 방문 그 자체가 중심이고, 백트래킹은 정답 후보를 만들면서 중간에 invalid 경로를 잘라내는 것이 중심입니다.
코딩테스트에서 어떤 신호가 보이면 백트래킹일까
- 모든 조합, 순열, 배치를 만들어 봐야 한다
- 중간 상태가 이미 불가능한지 빠르게 판단할 수 있다
- 부분 해가 쓸모없어지는 조건이 있다
- 끝까지 다 가지 않아도 버릴 수 있는 갈래가 많다
즉 “가능한 답을 만들다가, 중간에 틀린 길이면 더 안 들어간다”는 신호가 있으면 백트래킹 가능성이 큽니다.
자주 하는 실수
- DFS 순회를 하면서도 가지치기 조건을 전혀 안 넣는다
- 백트래킹인데 방문 복구를 안 한다
- 가능하지 않은 경로를 끝까지 다 본다
- 상태를 전역으로 바꾸고 복구하지 않아 결과가 꼬인다
백트래킹 문제에서는 방문 처리보다 복구 시점이 더 중요해질 때가 많습니다. 왜냐하면 다른 경로 탐색을 위해 상태를 되돌려야 하기 때문입니다.
탐색 흐름 비교는 BFS 글, 상태 정의 감각은 DP 글과도 이어집니다.
마무리
DFS와 백트래킹 차이를 짧게 말하면, DFS는 깊게 들어가는 탐색 방식이고 백트래킹은 그 탐색 과정에서 가능성이 없는 갈래를 빨리 버리는 전략입니다.
즉 두 용어를 덜 헷갈리려면, 지금 보고 있는 것이 방문 문제인가, 정답 후보 생성 문제인가를 먼저 구분하는 편이 가장 실용적입니다.
