백트래킹은 그래프 탐색에 있어, DFS와 같은 방향으로 쓰인다. DFS의 범주에 속하는, 변형이라고 보면 된다.
의미는 말 그대로, 탐색하다가 막힌 길이 나오면(더 갈 수 없으면) 왔던 길을 되돌아 간다.
더 이상 이 길에 가능성이 안 보이면, 그 길은 더 찾지 않고 다른 길을 찾는 것이 백트래킹이다.
쉽게 생각하면 DFS에서 전부 탐색하는 것이 아니라,
정답에 관한 조건을 두고, 부합하지 않는 부분은 가지 않는 것이다.
이처럼 답이 아닐 곳의 탐색을 덜어내는 것을 가지치기(pruning)라고 한다.
최악의 경우에는 모든 경우의 수를 거쳐서 답에 도달할 수도 있긴 하다.
제약 충족 문제(CSP)에 필수적이다. 위와 같이 제약 조건을 두고, 해당하지 않는 경우는 제외하기 때문이다.
그에 따라 반복문을 덜 돌 수 있으니, 시간 복잡도도 줄일 수 있다.
예시로, 스도쿠의 정답(상태)을 찾는 것을 들 수 있겠다. 이처럼, 규칙에 부합하는 경우만 탐색을 하게 된다.
십자 말풀이, 8퀸 문제, 4색 문제 등의 퍼즐 문제와 배낭 문제, 문자열 파싱, 조합 최적화 문제 등
위와 같은 것들이 모두 제약 충족 문제에 속한다고 한다.