백트래킹은 완전 탐색과 어떻게 다른가요?

백트래킹은 가능한 해를 탐색하다가 현재 선택이 더 이상 유효한 해로 이어질 수 없다고 판단되면 즉시 되돌아가는 탐색 기법입니다. 완전 탐색의 한 형태이지만, 가지치기(pruning)를 통해 불필요한 경우의 수를 줄인다는 점이 핵심 차이입니다.

핵심 개념

• 완전 탐색은 모든 후보를 끝까지 확인합니다.
• 백트래킹은 부분 해를 만들면서 제약 조건을 검사하고, 위반하면 더 깊이 가지 않습니다.
• 재귀 호출 전 선택하고, 호출 후 선택을 되돌리는 패턴이 많습니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

// 순열 생성에서 사용 여부를 추적하는 백트래킹
function permutations(nums) {
  const result = [];
  const used = Array(nums.length).fill(false);
  const path = [];

  function dfs() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      dfs();
      path.pop();
      used[i] = false;
    }
  }
  dfs();
  return result;
}

실무에서 주의할 점

• 가지치기 조건이 약하면 완전 탐색과 거의 같아져 시간 초과가 발생합니다.
• 상태를 되돌리는 코드를 빠뜨리면 다음 분기 탐색이 오염됩니다.
• 중복 원소가 있는 조합/순열은 중복 제거 조건을 추가해야 합니다.

실무 적용 가이드

• N-Queen, 스도쿠, 조합/순열, 제약 만족 문제에 적합합니다.
• 재귀 함수의 인자와 전역 상태를 명확히 분리합니다.
• 불가능 조건을 가능한 한 위쪽에서 검사해 탐색 공간을 줄입니다.

함께 연결해서 보면 좋은 키워드

Backtracking, Brute Force, Pruning, DFS

정리

백트래킹은 가능한 해를 탐색하다가 현재 선택이 더 이상 유효한 해로 이어질 수 없다고 판단되면 즉시 되돌아가는 탐색 기법입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.