백트래킹(Backtracking)

백트래킹(Backtracking): 완전 탐색을 효율적으로 만드는 탐색 전략

1. 서론

백트래킹(Backtracking)은 흔히 “느린 알고리즘”, “코딩 테스트에서만 쓰는 기법”으로 오해되곤 한다.
그러나 이는 백트래킹의 본질을 정확히 이해하지 못한 인식이다.

백트래킹은 모든 경우를 무작정 탐색하는 완전 탐색(Brute Force)이 아니라,
정답이 될 수 없는 경우를 가능한 한 빨리 제거(pruning)하여 탐색 공간을 줄이는 전략이다.

이 글에서는 백트래킹을 다음 관점에서 체계적으로 정리한다.

• 정확한 정의와 구조
• 상태 공간 트리와 가지치기
• 시간 복잡도에 대한 올바른 이해
• 대표 문제 유형
• DFS, 분할 정복, 동적 계획법과의 경계

 

2. 백트래킹의 정확한 정의

백트래킹(Backtracking)이란 다음과 같이 정의할 수 있다.

백트래킹은
해 공간(state space)을 트리 구조로 표현한 뒤,
가능한 해를 깊이 우선으로 탐색하면서
현재 상태가 문제의 제약 조건을 만족하지 못하면
해당 상태의 하위 탐색을 중단(pruning)하는
완전 탐색 기반 알고리즘 설계 기법이다.

이 정의에서 핵심 키워드는 다음 세 가지이다.

• 상태 공간 트리(State Space Tree)
• 부분 해(Partial Solution)
• 가지치기(Pruning)

즉, 백트래킹은 “탐색 방식”이 아니라
탐색 범위를 줄이기 위한 논리적 전략이다.

 

3. 백트래킹의 구조적 요소

3.1 상태(State)와 선택(Choice)

모든 백트래킹 문제는 다음 질문으로 환원할 수 있다.

1. 현재 상태는 무엇인가?
2. 다음 단계에서 가능한 선택지는 무엇인가?
3. 이 상태는 유효한가?

예를 들어 N-Queen 문제에서는:

• 상태: 현재까지 배치한 퀸의 위치
• 선택: 다음 행에 퀸을 놓을 열
• 유효성: 같은 열, 대각선 충돌 여부

상태 정의가 불명확하면
가지치기 조건 역시 명확해질 수 없다.

 

3.2 가지치기(Pruning)의 핵심 역할

백트래킹의 성능은
얼마나 많은 경우를 초기에 제거할 수 있는가에 의해 결정된다.

대표적인 가지치기 방식은 다음과 같다.

• 제약 조건 검사(Constraint Checking)
• 불가능한 부분 해 조기 종료
• 대칭 제거(Symmetry Breaking)

가지치기가 없는 백트래킹은
사실상 완전 탐색과 다르지 않다.

 

4. 시간 복잡도에 대한 올바른 이해

백트래킹 알고리즘은 일반적으로
최악의 경우 지수 시간 복잡도를 가진다.

예:

• N-Queen 문제: O(N!)
• 순열 생성: O(N!)
• 부분 집합 탐색: O(2ⁿ)

그러나 이는 어디까지나 최악의 경우에 대한 이론적 분석이다.
실제 수행 시간은 가지치기 효과에 따라 크게 달라진다.

중요한 점은 다음과 같다.

• 백트래킹은 최악 시간 복잡도를 개선하기 위한 기법이 아니다
• 탐색 공간 자체를 줄이기 위한 전략이다

 

5. 대표적인 백트래킹 문제 유형

5.1 N-Queen 문제

• 각 행마다 하나의 퀸을 배치
• 열, 대각선 충돌 시 즉시 가지치기

백트래킹의 상태 정의와 가지치기 효과를 설명하기에 가장 적합한 예제이다.

 

5.2 순열, 조합, 부분 집합

• DFS 기반 상태 확장
• 방문 여부 또는 시작 인덱스로 중복 제어

완전 탐색과 백트래킹의 차이를 설명하기에 적합한 문제군이다.

 

5.3 스도쿠(Sudoku)

• 제약 조건이 매우 명확
• 가지치기 효과가 극대화됨

실무 관점에서는
제약 조건 기반 탐색 문제의 대표 사례로 볼 수 있다.

 

6. DFS와 백트래킹의 차이

DFS와 백트래킹은 자주 혼용되지만, 개념적으로는 명확히 구분된다.

• DFS(Depth-First Search): 탐색 순서 및 구현 방식
• 백트래킹: 불필요한 탐색을 제거하는 전략

즉,
백트래킹은 DFS 위에서 동작하는 논리적 제약 조건 집합이라고 이해하는 것이 정확하다.

 

7. 백트래킹과 다른 알고리즘 설계 기법 비교

구분	백트래킹	분할 정복	동적 계획법
탐색 범위	경우의 수 기반	문제 분할	상태 공간
부분 문제 중복	있음	없음	있음
핵심 전략	가지치기	결합 비용	상태 정의
정답 보장	문제 의존	구조 의존	항상

이 비교를 통해
문제의 성격에 따라 어떤 설계 기법이 적합한지 판단할 수 있다.

 

8. 실무 및 코딩 테스트 관점의 판단 기준

다음 질문에 대부분 “예”라고 답할 수 있다면 백트래킹을 고려할 수 있다.

• 가능한 경우의 수가 명확한가?
• 부분 단계에서 정답 조건을 검증할 수 있는가?
• 모든 해 또는 하나의 해를 탐색해야 하는가?
• 가지치기 조건을 논리적으로 정의할 수 있는가?

이 중 하나라도 불명확하다면
백트래킹은 비효율적인 선택이 될 수 있다.

 

9. 결론

백트래킹은 느린 알고리즘이 아니다.
불필요한 탐색을 제거하는 전략이다.

성능의 핵심은 재귀 호출이 아니라
상태 정의와 가지치기 조건의 설계에 있다.

백트래킹을 제대로 이해했다는 것은
문제의 해 공간을 트리로 그릴 수 있고,
어디서 탐색을 중단해야 하는지 설명할 수 있다는 의미이다.