백트래킹(Backtracking)은 특정 문제의 모든 가능한 해를 찾기 위한 일반적인 알고리즘 기법입니다. 이는 본질적으로 깊이 우선 탐색(DFS)의 한 형태로, 해를 찾기 위해 모든 가능한 경로를 탐색하되, 특정 경로가 더 이상 해답으로 이어질 수 없다고 판단될 경우 즉시 해당 경로에서 되돌아와(backtrack) 다른 경로를 시도합니다. 백트래킹은 완전 탐색(exhaustive search)의 한 형태이며, 일반적으로 비효율적일 수 있지만, '가지치기(pruning)'라는 최적화 기법을 적용하여 불필요한 탐색을 줄일 수 있습니다.
백트래킹은 다음과 같은 다양한 유형의 문제를 해결하는 데 주로 사용됩니다:
- 조합 문제: 주어진 N개의 원소 중 K개를 선택하는 모든 방법 찾기
- 분할 문제: 문자열을 특정 규칙에 따라 분할하는 모든 방법 찾기
- 부분집합 문제: N개 원소의 집합에서 조건에 맞는 모든 부분집합 찾기
- 순열 문제: N개의 원소를 정해진 규칙에 따라 배열하는 모든 순열 찾기
- 보드 게임 문제: N-Queen, 스도쿠 등 퍼즐 해결
이러한 모든 백트래킹 문제들은 근본적으로 의사결정 과정을 나타내는 트리 구조로 추상화될 수 있습니다.
백트래킹 구현의 세 가지 핵심 요소
백트래킹 알고리즘을 구현할 때는 다음 세 가지 핵심 요소를 고려해야 합니다.
-
재귀 함수 서명 및 매개변수
백트래킹 재귀 함수는 현재까지의 상태, 남은 선택지, 그리고 최종 결과를 저장할 컨테이너 등 문제를 해결하는 데 필요한 모든 정보를 매개변수로 받아야 합니다.
def explore_path(current_state, available_choices, solution_collector): # ... 구현 ... -
재귀 함수 종료 조건
재귀 호출이 더 이상 진행될 수 없거나, 유효한 해답을 찾았을 때 함수가 종료되어야 합니다. 해답을 찾았다면 이를 결과 컬렉션에 추가하고 현재 재귀를 반환합니다.
if is_solution_found(current_state): solution_collector.add(current_state) return # 또는 if is_path_invalid(current_state): return -
탐색 및 되돌림 과정
현재 상태에서 가능한 모든 선택지를 반복(for 루프)하며 탐색을 진행합니다. 각 선택지에 대해:
- 선택: 현재 선택을 현재 상태에 반영합니다.
- 재귀: 다음 단계로 재귀 호출을 진행하여 더 깊이 탐색합니다.
- 되돌림: 재귀 호출이 반환된 후, 현재 선택을 취소(backtrack)하여 현재 상태를 원래대로 되돌립니다. 이는 다른 선택지를 탐색할 수 있도록 합니다.
for choice in possible_choices_at_current_step: # 선택 make_choice(current_state, choice) # 재귀 호출 (다음 단계 탐색) explore_path(updated_state, remaining_choices, solution_collector) # 되돌림 (선택 취소) undo_choice(current_state, choice)
아래 다이어그램은 백트래킹 알고리즘이 트리를 탐색하는 방식을 시각적으로 보여줍니다. for 루프는 각 노드의 '자식'들을 수평으로 탐색하며, 재귀 호출은 '깊이' 방향으로 수직 탐색을 진행합니다.
위의 세 단계를 통합한 일반적인 백트래킹 템플릿은 다음과 같습니다:
def solve_with_backtracking(parameters):
# 1. 종료 조건
if termination_condition_met(parameters):
store_result(parameters)
return
# 2. 탐색 과정 (for 루프: 너비, 재귀 호출: 깊이)
for choice in generate_possible_choices(parameters):
# 2a. 선택 (처리)
apply_choice(parameters, choice)
# 2b. 재귀 호출
solve_with_backtracking(updated_parameters)
# 2c. 되돌림 (선택 취소)
undo_choice(parameters, choice)
문제 예시: LeetCode 77. 조합 (Combinations)
주어진 두 정수 n과 k에 대해, 1부터 n까지의 숫자 중에서 k개의 숫자를 선택하여 만들 수 있는 모든 가능한 조합을 반환하는 문제입니다. 예를 들어, n = 4, k = 2라면 결과는 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]가 됩니다.
이 문제는 백트래킹을 사용하여 효율적으로 해결할 수 있습니다. 각 재귀 단계에서 현재 숫자를 조합에 추가할지 말지를 결정하고, 다음 숫자로 넘어가는 방식으로 트리를 탐색합니다.
백트래킹으로 조합 문제 해결
파이썬을 이용한 구현 예시는 다음과 같습니다:
from typing import List
class CombinationFinder:
def find_combinations(self, upper_bound: int, combo_length: int) -> List[List[int]]:
"""
1부터 upper_bound까지의 숫자 중에서 combo_length개의 숫자를 선택하는 모든 조합을 찾습니다.
"""
all_possible_combinations = []
# _explore_combinations 함수를 호출하여 백트래킹 탐색을 시작합니다.
# current_start는 1부터 시작하며, 빈 리스트가 초기 current_selection입니다.
self._explore_combinations(upper_bound, combo_length, 1, [], all_possible_combinations)
return all_possible_combinations
def _explore_combinations(self, n_max: int, k_len: int, current_start: int,
current_selection: List[int], collection_of_results: List[List[int]]):
"""
백트래킹을 통해 조합을 재귀적으로 탐색하는 헬퍼 함수입니다.
n_max: 선택할 수 있는 최대 숫자 (예: 4)
k_len: 조합의 길이 (예: 2)
current_start: 다음 숫자를 선택하기 시작할 숫자 (중복을 피하기 위해)
current_selection: 현재까지 선택된 숫자들로 구성된 조합
collection_of_results: 모든 유효한 조합을 저장할 리스트
"""
# 종료 조건: current_selection의 길이가 k_len과 같아지면 유효한 조합을 찾은 것입니다.
if len(current_selection) == k_len:
# 현재 조합의 복사본을 결과 리스트에 추가합니다. (참조 복사 방지)
collection_of_results.append(list(current_selection))
return
# 탐색 과정: current_start부터 n_max까지 숫자를 시도합니다.
# 주의: 이 시점에서 남아있는 요소의 개수와 현재 선택된 요소의 개수를 고려하여
# 더 이상 k_len 길이의 조합을 만들 수 없다면 조기에 종료하는 가지치기(pruning)를
# 추가할 수 있지만, 여기서는 기본적인 흐름을 따릅니다.
# (예: if n_max - current_start + 1 < k_len - len(current_selection): return)
for num_to_add in range(current_start, n_max + 1):
# 1. 선택: 현재 숫자를 조합에 추가합니다.
current_selection.append(num_to_add)
# 2. 재귀: 다음 숫자를 선택하기 위해 current_start를 num_to_add + 1로 설정하여 재귀 호출합니다.
self._explore_combinations(n_max, k_len, num_to_add + 1, current_selection, collection_of_results)
# 3. 되돌림: 재귀 호출이 완료된 후, 현재 숫자를 조합에서 제거하여 다른 가능성을 탐색합니다.
current_selection.pop()