기술사 학습노트 | imt-log

기술사 학습노트› 알고리즘› 백트래킹

Algorithm · 한장정리

[기술사토픽] 백트래킹(Backtracking) 완벽 정리 - 한장정리

백트래킹의 동작 원리, 유망성 검토, 상태공간트리, 가지치기(Pruning) 기법을 체계적으로 정리한 기술사 핵심 학습노트

백트래킹Backtracking깊이우선탐색DFS가지치기Pruning유망성검토상태공간트리정보관리기술사알고리즘

Ⅰ.개요

백트래킹(Backtracking)은 해를 찾는 도중 현재 경로가 해가 될 수 없다고 판단되면 되돌아가(Backtrack) 다른 경로를 탐색하는 알고리즘 기법이다. 완전 탐색(Brute Force)에 가지치기(Pruning)를 결합하여 탐색 공간을 효율적으로 줄인다.

핵심 개념

유망(Promising): 현재 노드에서 해를 찾을 가능성이 있는 상태.
가지치기(Pruning): 유망하지 않은 노드는 탐색하지 않고 부모 노드로 되돌아가는 과정.

구분	완전 탐색(Brute Force)	백트래킹
탐색 방식	모든 경우의 수 탐색	유망하지 않으면 중단
효율성	낮음 (O(n!) 수준)	상황에 따라 크게 향상
구현	단순 반복/재귀	DFS + 유망성 함수

Ⅱ.절차 및 동작 원리

백트래킹은 상태 공간 트리(State Space Tree)를 DFS 방식으로 탐색하며 유망성을 검토한다.

단계	내용
① 초기화	루트 노드에서 탐색 시작, 해 후보 집합 초기화
② 유망성 검사	현재 노드가 해가 될 수 있는지 조건 확인
③ 탐색 진행	유망하면 자식 노드로 재귀 탐색 진행
④ 가지치기	유망하지 않으면 현재 노드를 버리고 부모 노드로 복귀
⑤ 해 발견	모든 조건을 만족하는 노드를 해로 저장

의사코드:
backtrack(노드 v) {
  if (v가 유망하지 않음) return;
  if (v가 해) 해를 출력;
  for (v의 각 자식 w) backtrack(w);
}

Ⅲ.적용 사례

문제	유망성 조건	가지치기 효과
N-Queens	같은 행·열·대각선에 퀸이 없음	8-Queens: 2,057개 노드(완전탐색 40,320 대비)
부분집합 합	현재 합이 목표 초과하지 않음	조기 종료로 탐색 공간 대폭 감소
그래프 색칠	인접 정점과 색이 다름	불가 색 선택 시 즉시 되돌아감
미로 탐색	벽이 없고 방문하지 않은 경로	막힌 경로 즉시 포기
스도쿠	행·열·3×3 박스에 숫자 중복 없음	조기 충돌 감지로 불필요 탐색 제거

시험 포인트

백트래킹은 최악의 경우 완전 탐색과 동일하지만, 유망성 함수(Promising Function)의 설계에 따라 실제 탐색 노드 수가 크게 줄어든다. N-Queens 문제가 대표 기출 사례이며, DFS와의 차이점(유망성 검토 유무)을 명확히 구분해야 한다.

Ⅳ.결론

Conclusion

백트래킹은 DFS 기반의 탐색에 유망성 검토(Pruning)를 결합한 기법으로, 완전 탐색 대비 탐색 공간을 효율적으로 줄인다. 최적해보다 가능한 해 전체를 구하는 데 적합하며, N-Queens·부분집합 합·스도쿠 등 제약 만족 문제(CSP)에 널리 적용된다. 유망성 함수의 품질이 알고리즘 성능을 좌우하므로 강력한 Pruning 조건 설계가 핵심이다.

블로그: 기술사 학습노트 · imt-log.tistory.com

← 알고리즘 목록