백트래킹이란 무엇인가를 한 줄로 말하면, 정답 후보를 하나씩 만들어 가다가 더 볼 가치가 없는 갈래는 중간에 잘라내고 돌아오는 탐색 전략입니다. 코딩테스트에서 자주 보이는 재귀 코드가 모두 백트래킹은 아니며, 중간 제약을 검사해서 안 되는 길을 일찍 버리는가가 핵심 차이입니다.
이번 글에서는 백트래킹을 단순 문법이 아니라 선택, 검사, 탐색, 복구의 흐름으로 설명하겠습니다. 그리고 왜 DFS와 자꾸 헷갈리는지, 순열과 N-Queen 같은 문제에서 어떤 감각으로 적용해야 하는지도 단계적으로 정리하겠습니다.
백트래킹이란 무엇인가
백트래킹은 현재 상태에서 가능한 선택을 하나 고르고, 그 선택이 아직 유효한지 검사한 뒤, 괜찮으면 더 깊이 들어가 보고, 끝나면 다시 되돌리는 탐색 전략입니다. 이 흐름을 짧게 줄이면 선택 → 검사 → 탐색 → 복구입니다.
- 선택: 후보 하나를 고른다
- 검사: 지금 규칙을 깨지 않았는지 본다
- 탐색: 계속 가능하면 다음 단계로 내려간다
- 복구: 돌아오면서 방금 바꾼 상태를 원래대로 돌린다
중요한 점은 모든 경우를 끝까지 다 보지 않는다는 것입니다. 부분 해가 이미 틀렸다는 것이 드러나면 그 아래는 더 보지 않고 바로 돌아옵니다. 이 중간 탈락이 바로 가지치기입니다.
왜 DFS와 자꾸 헷갈릴까
백트래킹 코드는 재귀로 구현되는 경우가 많아서 DFS와 모양이 비슷합니다. 하지만 중심 질문은 다릅니다. DFS는 어떤 순서로 방문할지를 다루고, 백트래킹은 이 선택을 계속 밀고 가도 정답이 될 가능성이 있는지를 다룹니다.
- DFS: 깊게 들어가는 탐색 방식
- 백트래킹: 안 되는 가지를 일찍 버리는 탐색 전략
- 공통점: 재귀 구조를 자주 쓴다
- 차이점: 방문보다 중간 제약 검사와 복구가 더 중요하다
DFS 기본 개념은 깊게 들어갔다가 되돌아오는 흐름으로 설명됩니다. 여기에 정답 후보 생성과 가지치기까지 붙으면 백트래킹의 성격이 강해집니다. 더 직접적인 비교는 DFS와 백트래킹 차이 글을 함께 보면 분명해집니다.
코딩테스트에서 백트래킹이 먼저 떠오르는 문제 신호
- 순열, 조합, 부분집합처럼 후보를 만들어 가야 한다
- 중간 상태만 보고도 이미 실패인지 판단할 수 있다
- 한 번 고른 선택을 나중에 취소하고 다른 선택을 다시 시도해야 한다
- 답을 한 번에 계산하기보다 경로를 채워 가는 느낌이 강하다
대표 예시는 순열 생성, 조합 생성, 부분집합 탐색, N-Queen, 스도쿠 같은 제약 충족 문제입니다. 공통점은 답을 한 번에 계산하지 않고, 후보를 조금씩 만들며 안 되는 길을 중간에 버린다는 점입니다.
선택, 검사, 탐색, 복구 흐름을 순열 예시로 이해하기
숫자 1, 2, 3으로 길이 2인 순열을 만든다고 해 보겠습니다. 빈 경로에서 시작해 1을 고르면 경로는 [1]이 됩니다. 다음 자리에서는 1을 또 쓸 수 없으므로 2나 3만 고를 수 있습니다.
여기서 [1, 2]를 확인한 뒤에는 다시 [1]로 돌아와야 [1, 3]도 시도할 수 있습니다. 그리고 [1]도 다 봤다면 다시 []로 돌아와서 2를 첫 번째 원소로 고릅니다. 이처럼 한 선택을 시험해 본 뒤 흔적을 지우고 다음 선택을 다시 시험하는 구조가 백트래킹의 핵심입니다.
코드 예시: 길이 M 순열 만들기
아래 코드는 1부터 N까지 숫자 중에서 길이 M의 순열을 만드는 전형적인 백트래킹 예시입니다. 핵심은 재귀 호출 자체보다, 들어가기 전 상태 변경과 돌아온 뒤 복구입니다.
n = 3
m = 2
path = []
used = [False] * (n + 1)
result = []
def backtrack():
if len(path) == m:
result.append(path[:])
return
for num in range(1, n + 1):
if used[num]:
continue
used[num] = True
path.append(num)
backtrack()
path.pop()
used[num] = False
backtrack()
print(result)이 코드에서 반드시 봐야 하는 줄은 path.pop()과 used[num] = False입니다. 이 두 줄이 없으면 다음 후보를 탐색할 때 이전 선택이 남아서 결과가 꼬입니다.
가지치기는 어디서 일어날까
백트래킹을 백트래킹답게 만드는 것은 가지치기입니다. 예를 들어 숫자 합이 정확히 10이어야 하는데 현재 합이 이미 10을 넘었다면, 그 아래를 더 봐도 답이 될 수 없습니다. 이때 바로 return 해서 탐색을 끊으면 됩니다.
def backtrack(total, idx):
if total > 10:
return
if total == 10:
print("answer")
return
for nxt in range(idx, 6):
backtrack(total + nxt, nxt + 1)이 예시에서 if total > 10: return이 가지치기입니다. 다만 가지치기가 약하면 최악의 경우 여전히 많은 상태를 봐야 하므로, 백트래킹을 만능 최적화처럼 이해하면 안 됩니다.
N-Queen에서 백트래킹이 잘 보이는 이유
N-Queen은 한 행에 퀸을 하나 놓고 내려가다가, 같은 열이나 대각선 충돌이 생기면 그 아래 행은 더 볼 필요가 없다는 점에서 백트래킹 감각이 가장 선명하게 드러나는 문제입니다.
- 현재 행에 놓을 열을 고른다
- 기존 퀸과 충돌하는지 검사한다
- 가능하면 다음 행으로 내려간다
- 돌아오면 방금 놓은 퀸을 없애고 다른 열을 본다
즉 N-Queen은 선택, 검사, 탐색, 복구라는 네 단계를 거의 교과서처럼 보여 주는 대표 예시입니다.
자주 하는 실수
- 재귀로 깊게 들어간다고 모두 백트래킹이라고 생각한다
- 방문 배열이나 경로 복구를 빼먹는다
- 정답을 하나만 찾을지 전부 찾을지 종료 조건을 흐리게 둔다
- 틀린 것이 이미 분명한데도 가지치기를 너무 늦게 한다
문제를 읽을 때는 답을 한 번에 계산하는 문제인지, 후보를 만들어 가는 문제인지부터 구분해 보세요. 그리고 중간 상태만 보고도 실패를 알 수 있는지, 복구해야 할 값이 무엇인지 적어 보면 백트래킹 여부가 훨씬 또렷해집니다.
비슷하게 선택 상태를 압축해서 다뤄야 하는 문제는 비트마스킹은 코딩테스트에서 언제 필요한가도 함께 보면 좋습니다. 원소 선택 여부를 visited 배열 대신 비트로 표현하는 방식은 백트래킹 문제와 자주 연결됩니다.
정리
백트래킹이란 무엇인가를 다시 짧게 정리하면, 정답 후보를 조금씩 만들다가 중간에 틀린 길은 더 깊이 보지 않고 잘라내며, 재귀 호출 뒤에는 상태를 복구하는 탐색 전략입니다. DFS 모양으로 구현되는 경우가 많지만, 핵심은 방문 순서보다 가지치기와 복구입니다.
그래서 코딩테스트에서 백트래킹을 이해하는 가장 좋은 방법은 용어를 외우는 것이 아니라, 문제 위에 선택 → 검사 → 탐색 → 복구라는 네 단계를 직접 올려 보는 것입니다. 이 감각이 잡히면 순열, 조합, 부분집합, N-Queen 같은 문제를 볼 때 왜 여기서 백트래킹을 쓰는지 훨씬 덜 추상적으로 느껴집니다.
