왜 백트래킹이 필요한가
완전 탐색은 가능한 모든 후보를 검사합니다. 후보가 적을 때는 가장 확실한 방법입니다. 하지만 후보가 많아지면 금방 느려집니다.
예를 들어 서로 다른 숫자 10개를 한 줄로 나열하는 모든 순서를 생각해 봅시다. 첫 번째 자리에 10가지, 두 번째 자리에 9가지, 세 번째 자리에 8가지가 가능합니다. 전체 경우의 수는 10 × 9 × 8 × ... × 1입니다. 숫자가 조금만 늘어도 검사해야 할 경우가 폭발적으로 많아집니다.
백트래킹은 이런 상황에서 사용합니다. 백트래킹은 모든 가능성을 탐색하되, 더 진행해도 답이 될 수 없는 길은 일찍 포기합니다. 즉, 완전 탐색보다 똑똑하게 후보를 줄이는 방법입니다.
쉬운 예로 비밀번호를 찾는 상황을 생각해 봅시다. 네 자리 비밀번호를 왼쪽부터 맞춰 보는데, 두 번째 자리까지 입력한 순간 이미 규칙에 어긋난다면 나머지 두 자리를 시도할 필요가 없습니다. 그 자리에서 돌아가 다른 선택을 해 보면 됩니다.
백트래킹의 핵심 흐름은 다음 네 단계입니다.
하나를 선택한다.
그 선택으로 다음 단계로 진행한다.
가능성이 없으면 되돌아온다.
다른 선택을 시도한다.
이때 "되돌아온다"는 말이 중요합니다. 현재 선택을 취소하고 이전 상태로 복구해야 다음 후보를 올바르게 검사할 수 있습니다.
AI 생성 이미지
백트래킹의 기본 구조
백트래킹은 보통 재귀 함수로 구현합니다. 재귀는 한 단계 선택한 뒤, 같은 방식으로 다음 단계를 처리하기에 잘 맞습니다.
기본 형태는 다음과 같습니다.
function search(state):
if state가 완성된 답이라면:
답을 기록한다
return
for choice in 가능한 선택들:
if choice가 현재 상태에서 불가능하다면:
continue
choice를 적용한다
search(다음 상태)
choice를 취소한다여기서 state는 현재까지 만든 상태입니다. 예를 들어 지금까지 고른 숫자 목록, 체스판에 놓은 퀸의 위치, 퍼즐에서 채운 칸들이 상태가 될 수 있습니다.
choice를 적용한다는 것은 현재 후보를 추가하는 일입니다. choice를 취소한다는 것은 재귀 호출이 끝난 뒤, 방금 추가한 후보를 제거하는 일입니다. 이 과정을 제대로 하지 않으면 다음 탐색이 이전 탐색의 흔적에 영향을 받습니다.
백트래킹은 다음 질문으로 생각하면 쉽습니다.
지금까지 만든 것이 답이 되었는가?
아직 답이 아니라면, 다음에 무엇을 선택할 수 있는가?
그 선택은 문제 조건을 어기지 않는가?
탐색이 끝난 뒤 상태를 원래대로 돌렸는가?
순열 만들기: 사용한 원소를 표시하기
순열은 순서가 중요한 나열입니다. 예를 들어 [A, B, C]로 길이 3의 순열을 만들면 다음과 같은 결과가 나옵니다.
A B C
A C B
B A C
B C A
C A B
C B A순열에서는 같은 원소를 두 번 쓰면 안 됩니다. 그래서 어떤 원소를 이미 사용했는지 표시해야 합니다.
작은 예로 [A, B, C]에서 순열을 만드는 흐름을 보겠습니다.
첫 자리에
A를 고른다.A는 사용했다고 표시한다.두 번째 자리에는 남은
B,C중 하나를 고른다.세 번째 자리까지 채우면 답을 기록한다.
다시 돌아와 마지막 선택을 취소하고 다른 선택을 시도한다.
의사코드는 다음과 같습니다.
items = [A, B, C]
used = [false, false, false]
selected = []
function make_permutation():
if length(selected) == length(items):
print(selected)
return
for i from 0 to length(items) - 1:
if used[i] == true:
continue
used[i] = true
selected.append(items[i])
make_permutation()
selected.pop()
used[i] = false여기서 중요한 부분은 마지막 두 줄입니다.
selected.pop()
used[i] = false재귀 호출이 끝났다는 것은 items[i]를 선택한 경우의 탐색이 끝났다는 뜻입니다. 이제 다른 원소를 선택해 보려면, 방금 선택했던 원소를 목록에서 빼고 사용 표시도 해제해야 합니다.
이 해제 과정이 없으면 A를 한 번 사용한 뒤 계속 사용 중인 상태로 남습니다. 그러면 B A C처럼 A가 나중에 등장해야 하는 경우를 만들 수 없습니다.
조합 만들기: 시작 위치로 중복을 막기
조합은 순서가 중요하지 않은 선택입니다. [A, B, C]에서 2개를 고르는 조합은 다음 세 가지입니다.
A B
A C
B C순열에서는 A B와 B A가 다른 결과입니다. 하지만 조합에서는 둘을 같은 선택으로 봅니다. 따라서 조합을 만들 때는 이미 지나간 원소를 다시 고르지 않도록 해야 합니다.
가장 간단한 방법은 start를 사용하는 것입니다. start는 다음 선택을 어디서부터 볼지 나타내는 인덱스입니다.
items = [A, B, C, D]
selected = []
k = 2
function make_combination(start):
if length(selected) == k:
print(selected)
return
for i from start to length(items) - 1:
selected.append(items[i])
make_combination(i + 1)
selected.pop()예를 들어 첫 번째로 B를 골랐다면, 다음에는 C, D만 확인합니다. 다시 A로 돌아가지 않습니다. 그래서 B A 같은 중복 조합이 생기지 않습니다.
순열과 조합의 차이는 다음처럼 정리할 수 있습니다.
순열: 순서가 중요하다. 이미 사용한 원소를 다시 쓰지 않기 위해
used가 필요하다.조합: 순서가 중요하지 않다. 이전 위치로 돌아가지 않기 위해
start가 필요하다.
두 문제 모두 재귀로 만들 수 있지만, 중복을 막는 방식이 다릅니다.
가지치기: 답이 될 수 없는 길을 일찍 버리기
백트래킹의 힘은 가지치기에서 나옵니다. 가지치기는 탐색 중인 후보가 더 이상 답이 될 수 없다고 판단되면 그 아래 경우를 보지 않는 것입니다.
예를 들어 양수 목록에서 몇 개를 골라 합이 8이 되는 경우를 찾는다고 합시다.
numbers = [2, 3, 5, 9]
target = 8현재까지 2 + 3 + 5 = 10을 골랐다면 이미 목표 8을 넘었습니다. 모든 숫자가 양수라면, 여기서 숫자를 더 골라도 합은 더 커질 뿐입니다. 따라서 이 길은 더 볼 필요가 없습니다.
function search(index, current_sum):
if current_sum == target:
답을 찾았다
return
if current_sum > target:
return
for i from index to length(numbers) - 1:
search(i + 1, current_sum + numbers[i])이 코드는 current_sum > target이 되는 순간 바로 돌아옵니다. 이것이 가지치기입니다.
단, 가지치기 조건은 항상 안전해야 합니다. 위 예시는 모든 숫자가 양수일 때만 안전합니다. 음수가 섞여 있다면 현재 합이 목표보다 커졌더라도 나중에 음수를 더해 다시 줄어들 수 있습니다. 그런 경우 current_sum > target이라는 이유만으로 포기하면 정답을 놓칠 수 있습니다.
좋은 가지치기는 두 조건을 만족해야 합니다.
답이 될 수 없는 경우만 제거한다.
검사 비용이 너무 크지 않다.
가지치기 자체가 너무 복잡하면, 줄이는 시간보다 검사하는 시간이 더 커질 수 있습니다.
N-Queen 문제로 보는 백트래킹
백트래킹의 대표 예제는 N-Queen 문제입니다. N-Queen은 N × N 체스판에 퀸 N개를 놓되, 서로 공격할 수 없게 배치하는 문제입니다.
퀸은 같은 행, 같은 열, 같은 대각선에 있는 말을 공격할 수 있습니다. 따라서 퀸을 놓을 때 다음 조건을 확인해야 합니다.
같은 열에 이미 퀸이 있으면 안 된다.
왼쪽 위에서 오른쪽 아래로 이어지는 대각선에 퀸이 있으면 안 된다.
오른쪽 위에서 왼쪽 아래로 이어지는 대각선에 퀸이 있으면 안 된다.
한 행에 퀸을 하나씩만 놓는다고 정하면, 같은 행 조건은 자동으로 해결됩니다. 이제 각 행마다 어느 열에 놓을지만 선택하면 됩니다.
예를 들어 4개의 행을 위에서부터 차례대로 처리한다고 합시다.
0번 행에 퀸을 하나 놓는다.
1번 행에서 가능한 열을 찾는다.
가능하면 놓고 다음 행으로 간다.
어떤 행에서 놓을 곳이 없으면 이전 행으로 돌아간다.
이전 행의 퀸을 다른 열에 놓아 본다.
이 흐름이 바로 백트래킹입니다.
대각선 판단은 인덱스 규칙을 이용하면 간단해집니다.
같은
row - col값을 가지면 같은 대각선에 있다.같은
row + col값을 가지면 다른 방향의 같은 대각선에 있다.
의사코드는 다음과 같습니다.
count = 0
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
function place(row):
if row == n:
count = count + 1
return
for col from 0 to n - 1:
if col in cols:
continue
if row - col in diag1:
continue
if row + col in diag2:
continue
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
place(row + 1)
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)이 코드는 모든 칸 조합을 무작정 확인하지 않습니다. 한 행에 하나씩 놓고, 놓는 순간 열과 대각선 충돌을 확인합니다. 충돌이 있으면 그 아래 행들은 아예 탐색하지 않습니다.
예를 들어 0번 행 0번 열에 퀸을 놓고, 1번 행 2번 열에 퀸을 놓았다고 합시다. 이후 2번 행에서 어떤 열도 안전하지 않다면, 3번 행은 볼 필요가 없습니다. 바로 1번 행으로 돌아가 다른 열을 시도합니다.
이처럼 백트래킹은 "끝까지 가 보고 틀렸는지 확인"하는 방식이 아닙니다. "가는 도중에 이미 틀렸다면 멈추는" 방식입니다.
탐색 순서가 실행 시간을 바꾼다
백트래킹은 같은 문제라도 탐색 순서에 따라 실행 시간이 크게 달라질 수 있습니다.
예를 들어 퍼즐을 푼다고 생각해 봅시다. 선택지가 많은 칸부터 채우면 잘못된 길을 오래 탐색할 가능성이 큽니다. 반대로 선택지가 거의 없는 칸부터 채우면, 불가능한 경우를 빨리 발견할 수 있습니다.
N-Queen에서는 행을 하나씩 내려가며 놓는 방식이 기본입니다. 여기서 열과 대각선 충돌을 즉시 검사하면 많은 후보가 제거됩니다. 만약 퀸을 모두 대충 놓은 뒤 마지막에 한꺼번에 검사한다면, 불가능한 배치를 너무 많이 만들게 됩니다.
조합 합 문제에서도 숫자가 정렬되어 있고 모두 양수라면, 현재 합이 목표를 넘는 순간 이후 탐색을 멈출 수 있습니다. 정렬을 이용하면 "뒤의 숫자는 더 크므로 더 볼 필요가 없다"는 판단도 가능해집니다.
탐색 순서를 정할 때는 다음 기준을 생각해 볼 수 있습니다.
조건을 빨리 위반할 가능성이 큰 선택을 먼저 검사한다.
선택지가 적은 위치부터 채운다.
현재 선택이 이후 선택에 큰 영향을 주는 경우를 먼저 결정한다.
가지치기 조건을 빨리 적용할 수 있도록 상태를 관리한다.
백트래킹의 시간 복잡도는 보통 간단히 하나의 식으로 끝나지 않습니다. 최악의 경우 여전히 매우 많은 후보를 볼 수 있습니다. 하지만 좋은 가지치기를 넣으면 실제 실행 시간은 크게 줄어듭니다.
자주 틀리는 부분
첫째, 되돌리기를 빼먹기 쉽습니다. append를 했다면 재귀 호출 뒤에 pop을 해야 합니다. used[i] = true로 표시했다면 나중에 used[i] = false로 해제해야 합니다. 백트래킹에서 적용과 취소는 한 쌍입니다.
둘째, 종료 조건의 위치를 잘못 두는 경우가 있습니다. 답이 완성되었는지 먼저 확인해야 하는 문제도 있고, 불가능한 상태인지 먼저 확인해야 하는 문제도 있습니다. 중요한 것은 현재 상태가 답인지, 더 진행할 수 있는지의 순서를 문제 조건에 맞게 정하는 것입니다.
셋째, 순열과 조합을 혼동할 수 있습니다. 순열은 A B와 B A를 다르게 봅니다. 조합은 둘을 같은 선택으로 봅니다. 이 차이에 따라 used를 쓸지, start를 쓸지가 달라집니다.
넷째, 가지치기를 너무 강하게 하면 정답을 놓칩니다. 가지치기는 "확실히 답이 될 수 없는 경우"에만 해야 합니다. 조금 의심스럽다는 이유로 후보를 버리면 안 됩니다.
다섯째, 결과를 저장할 때 현재 목록 자체를 그대로 넣어 문제가 생길 수 있습니다. 많은 언어에서 목록은 참조로 전달됩니다. 그래서 답을 저장할 때는 현재 목록의 복사본을 저장해야 합니다.
answers.append(copy(selected))그냥 answers.append(selected)처럼 저장하면, 나중에 selected가 바뀔 때 저장된 답도 함께 바뀌는 문제가 생길 수 있습니다.
정리
백트래킹은 가능한 해를 탐색하는 방법입니다. 완전 탐색처럼 후보를 빠짐없이 고려하지만, 답이 될 수 없는 길은 중간에 포기합니다.
핵심 흐름은 선택, 진행, 되돌리기, 다른 선택 시도입니다. 순열에서는 사용한 원소를 표시하고 해제합니다. 조합에서는 시작 위치를 넘겨 중복 선택을 막습니다. N-Queen 같은 문제에서는 열과 대각선 조건을 이용해 불가능한 배치를 일찍 제거합니다.
백트래킹 문제를 만나면 먼저 이렇게 질문해 보세요.
한 단계에서 무엇을 선택하는가?
언제 답이 완성되는가?
어떤 선택은 더 진행하지 않아도 되는가?
재귀 호출 후 무엇을 원래대로 되돌려야 하는가?
이 네 질문에 답할 수 있다면, 복잡해 보이는 탐색 문제도 차근차근 코드로 옮길 수 있습니다.
이 노트는 보도·비평·교육·연구 목적으로 작성되었습니다. 저작권 문의가 있으시면 에서 알려주세요.