프로그래밍을 하다 보면 "모든 경우의 수를 탐색해야 하는 문제"를 자주 만나게 됩니다. 이럴 때 유용하게 쓰이는 기법 중 하나가 바로 백트래킹(Backtracking)입니다.
백트래킹은 말 그대로 "되돌아가기"입니다. 어떤 문제를 풀기 위해 가능한 선택지를 따라가다가, 그 선택이 정답으로 이어지지 않으면 다시 돌아가 다른 선택지를 탐색하는 방식입니다.
즉, 가능한 모든 경우를 탐색하지만, 유망하지 않은 경로는 조기에 포기(가지치기)하면서 효율적으로 답을 찾아나갑니다.
완전탐색의 일종이지만, 불필요한 경우를 줄이는 전략을 포함하고 있는 것이 차별점입니다.
Q. 언제 백트래킹을 사용하지?
- 가능한 모든 조합, 순열, 부분집합 등을 구해야 할 때
- 퍼즐, 미로 찾기, N-Queen, 스도쿠 등에서
- 탐색 과정에서 제약 조건을 만족해야 하는 문제들
기본 구조
def backtrack(상태):
if 정답 조건 만족:
정답 처리
return
for 선택 in 가능한 선택지:
if 유망한 선택인지 확인:
선택 수행
backtrack(다음 상태)
선택 되돌리기 (백트래킹)
예제 : 1부터 N까지 수 중에서 M개를 고른 모든 조합 (순서 상관 X)
def backtrack(start, path):
if len(path) == M:
print(path)
return
for i in range(start, N + 1):
path.append(i)
backtrack(i + 1, path)
path.pop() # 백트래킹
N = 4
M = 2
backtrack(1, [])백트래킹의 성능을 결정짓는 핵심은 가지치기입니다. 탐색 도중 "이 경로는 정답이 될 수 없다"는 판단이 서면, 더 깊은 탐색을 진행하지 않고 즉시 중단함으로써 불필요한 연산을 줄일 수 있습니다. 이를 통해 시간 복잡도를 크게 개선할 수 있습니다.
또한 백트래킹은 단순한 완전탐색과는 다릅니다. 가능한 모든 경우를 확인하되, 조건을 활용해 비효율적인 경로는 과감히 생략함으로써, 정답을 보장하면서도 효율성을 확보할 수 있는 탐색 기법입니다.