백트래킹 문제를 처음 만나면 이런 생각이 들 수 있습니다.
모든 경우를 다 보면 되나?
어디서 멈춰야 하지?
이건 DFS랑 뭐가 다른 거지?
겉보기에는 "경우의 수를 전부 시도하는 문제"처럼 보이지만, 실제로는 불가능한 경로를 얼마나 빨리 잘라내느냐가 핵심입니다.
이번 글에서는 백트래킹 문제를 만났을 때 어떻게 접근해야 하는지 감을 잡을 수 있도록 기본 판단 기준과 공통 구조를 정리해보겠습니다.
백트래킹이란?
백트래킹은 가능한 선택을 하나씩 시도해 보다가, 현재 경로가 더 이상 답이 될 수 없다고 판단되면 즉시 되돌아가는 방식입니다.
즉, 단순 DFS와 비슷하게 내려가지만 차이는 다음에 있습니다.
이 경로는 이미 틀렸다고 알면
더 깊이 들어가지 않고 바로 중단한다.
이 중단 과정을 보통 가지치기(pruning) 라고 부릅니다.
언제 백트래킹을 떠올리면 좋을까?
보통 아래 같은 특징이 있으면 백트래킹 후보일 가능성이 큽니다.
- 가능한 선택지가 여러 개 있다
- 순서대로 하나씩 선택해 나간다
- 중간 상태만 보고도 이미 틀렸는지 판단할 수 있다
- 완성된 답 하나 또는 가능한 답의 개수를 구한다
예를 들면:
- N-Queen
- 스도쿠
- 조합/순열 생성
- 미로 찾기
- 제약 조건이 있는 배치 문제
이런 문제들은 "답을 조금씩 만들 수 있고", "중간에 실패를 감지할 수 있다"는 공통점이 있습니다.
먼저 던질 3가지 질문
백트래킹 문제를 만나면 아래 3가지를 먼저 생각하면 좋습니다.
1. 부분 해를 조금씩 만들 수 있는가?
백트래킹은 정답을 한 번에 만드는 것이 아니라, 조금씩 쌓아 가는 방식입니다.
예를 들어 N-Queen이라면:
1행에 하나 놓고
2행에 하나 놓고
3행에 하나 놓고
...
스도쿠라면:
빈 칸 하나 채우고
다음 빈 칸 채우고
...
즉, "현재까지 만든 불완전한 상태"를 표현할 수 있어야 합니다.
2. 현재 경로가 이미 틀렸는지 알 수 있는가?
이게 백트래킹의 핵심입니다.
부분 해가 완성되지 않았더라도, 지금 상태만 보고 더 진행할 가치가 없는지 판단할 수 있어야 합니다.
예를 들면:
- N-Queen: 방금 놓은 퀸이 다른 퀸과 충돌하면 실패
- 스도쿠: 같은 행/열/박스에 같은 숫자가 겹치면 실패
- 조합 문제: 합이 목표를 이미 초과하면 실패
이 판단이 가능해야 가지치기가 됩니다.
반대로 "끝까지 가보기 전에는 실패인지 성공인지 전혀 모른다"면 백트래킹의 장점이 크게 줄어듭니다.
3. 언제 답이 완성됐는지 알 수 있는가?
탐색을 계속하다가 "이제 정답 하나가 완성됐다"는 시점도 분명해야 합니다.
예를 들어:
- N개의 퀸을 다 놓았을 때
- 모든 빈 칸을 다 채웠을 때
- 원하는 길이의 문자열을 만들었을 때
- 모든 항목을 한 번씩 다 사용했을 때
이 종료 조건이 명확해야 현재 경로를 정답으로 처리할 수 있습니다.
공통 템플릿으로 보면 더 쉬워진다
백트래킹 문제는 겉모습이 달라도 대개 아래 템플릿 안에 들어옵니다.
def backtrack(state):
if complete(state):
record_answer(state)
return
for choice in choices(state):
apply(choice, state)
if valid(state):
backtrack(state)
undo(choice, state)
핵심 흐름은 이렇습니다.
선택한다
-> 유효하면 더 내려간다
-> 끝까지 갔으면 답 처리
-> 돌아오면서 선택을 원상복구한다
이 undo 단계 때문에 백트래킹이라는 이름이 붙습니다.
아주 간단한 예시로 보기
예를 들어 숫자 1부터 3까지를 사용해서 길이 2인 순열을 만든다고 해보겠습니다.
가능한 답은 다음과 같습니다.
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]
이 경우 백트래킹은 다음처럼 생각할 수 있습니다.
현재까지 선택한 숫자 목록을 들고 간다
이미 쓴 숫자는 다시 고르지 않는다
길이가 2가 되면 답으로 저장한다
코드는 이렇게 쓸 수 있습니다.
def permutations_of_length_two():
result = []
path = []
used = [False, False, False, False]
def backtrack():
if len(path) == 2:
result.append(path[:])
return
for num in range(1, 4):
if used[num]:
continue
path.append(num)
used[num] = True
backtrack()
used[num] = False
path.pop()
backtrack()
return result
여기서도 구조는 똑같습니다.
- 숫자를 하나 고른다
- 이미 쓴 숫자면 건너뛴다
- 길이가 2가 되면 답으로 저장한다
- 돌아오면서 선택을 취소한다
백트래킹과 DFS의 차이
백트래킹은 DFS를 사용해서 구현하는 경우가 많습니다.
그래서 둘이 같은 말처럼 느껴질 수 있습니다.
하지만 관점은 조금 다릅니다.
- DFS: 깊이 우선으로 내려가는 탐색 방식
- 백트래킹: 내려가다가 틀린 경로를 빠르게 잘라내는 문제 해결 방식
즉:
백트래킹은 DFS를 도구로 자주 사용하지만,
핵심은 가지치기와 원상복구에 있다.
가지치기가 중요한 이유
백트래킹 문제는 경우의 수가 커지기 쉽습니다.
예를 들어 선택지가 N개 있고 깊이도 N이면,
아무 생각 없이 전부 탐색하면 매우 느려질 수 있습니다.
그래서 중요한 것은:
어차피 실패할 경로를 최대한 빨리 버리는 것
입니다.
좋은 백트래킹 풀이일수록
valid() 검사를 빨리 하고,
불필요한 탐색을 줄이는 방향으로 구성됩니다.
자주 나오는 실수
1. 선택 취소를 안 하는 경우
백트래킹은 내려간 뒤 다시 돌아와야 합니다.
따라서 아래 두 줄은 거의 세트입니다.
path.append(x)
path.pop()
또는
used[x] = True
used[x] = False
이걸 빼먹으면 다음 분기 탐색이 꼬입니다.
2. 유효성 검사를 너무 늦게 하는 경우
가능하면 빨리 실패를 감지해야 합니다.
예를 들어 N-Queen이라면 모든 퀸을 다 놓고 나서 검사하는 것보다, 퀸 하나를 놓을 때마다 검사하는 쪽이 훨씬 낫습니다.
3. 종료 조건이 애매한 경우
현재 상태가 언제 완성인지 명확하지 않으면 정답 처리 시점이 꼬이기 쉽습니다.
그래서 먼저 아래를 확실히 정해야 합니다.
언제 재귀를 멈출 것인가?
언제 답으로 저장할 것인가?
문제를 보면 이렇게 정리해보면 좋다
백트래킹 문제를 만나면 바로 코드부터 쓰기보다, 아래 4가지를 먼저 적어보면 훨씬 편합니다.
1. 상태(state)는 무엇인가?
2. 선택(choice)은 무엇인가?
3. 유효성 검사(valid)는 무엇인가?
4. 완료 조건(complete)은 무엇인가?
예를 들어 스도쿠라면:
state: 현재까지 채운 보드
choice: 빈 칸에 넣을 숫자
valid: 행/열/박스에 중복이 없는가
complete: 빈 칸이 더 이상 없는가
이렇게 정리되면 코드 구조가 훨씬 명확해집니다.
정리
백트래킹은 "모든 경우를 다 보는 무식한 방법"이 아니라, 답이 될 수 없는 경로를 빨리 포기하면서 탐색하는 방법입니다.
문제를 보면 먼저 아래 3가지를 확인해보면 좋습니다.
부분 해를 만들 수 있는가?
중간에 실패를 판별할 수 있는가?
완성된 답인지 확인할 수 있는가?
이 질문들에 답할 수 있다면 그 문제는 백트래킹으로 깔끔하게 풀릴 가능성이 큽니다.
한 줄로 요약하면 이렇습니다.
조금 만들고,
틀리면 바로 되돌아가고,
끝까지 가면 답으로 기록한다.
처음에는 재귀 호출 흐름이 낯설 수 있지만, 상태·선택·유효성·종료 조건을 분리해서 보면 백트래킹 문제를 훨씬 덜 막히고 풀 수 있습니다.