pkglog
EN

백트래킹: 가지치기로 모든 경우의 수를 줄이는 방법과 N-Queen·순열·조합

작성 · · 40분 읽기 · 수정 중급 튜토리얼

이 글의 핵심

백트래킹은 모든 경우의 수를 탐색하되 조건을 만족하지 않는 분기는 즉시 포기(가지치기)하는 알고리즘입니다. 이 글은 순열·조합·부분집합 같은 기본 패턴부터 N-Queen·스도쿠 같은 제약 만족 문제, 그리고 되돌리기 누락·가지치기 누락처럼 실무에서 자주 겪는 실수까지 정리합니다.

시리즈 안내

#11 | 📋 전체 목차 | 이전: #10 BFS와 DFS · 다음: #12 DP 기초

들어가며

백트래킹은 모든 경우의 수를 탐색하되, 조건 불만족 시 즉시 포기하는 알고리즘입니다. DFS와 유사하지만 가지치기(Pruning)를 통해 불필요한 탐색을 건너뜁니다.

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 “이 조건을 만족하는 모든 경우를 빠짐없이 찾아야 하는” 요구사항(권한 조합 검증, 설정 값 조합 테스트 등)을 만나면, 완전 탐색과 가지치기를 구분하는 감각이 얼마나 중요한지 깨닫게 됩니다. 가지치기 없이 모든 경우를 다 확인하도록 짠 코드가 입력이 조금만 커져도 시간 초과로 멈춰버리는 걸 겪어봐야, 왜 백트래킹이 단순 완전 탐색과 다른 접근인지 체감됩니다.

사전 지식 (초보자를 위한 기초)

재귀(Recursion) 복습

백트래킹은 재귀를 기반으로 합니다. 재귀가 낯설다면 먼저 이해하고 오세요.

# 재귀 예시: 1부터 n까지 출력
def print_numbers(n):
    if n == 0:  # 기저 조건 (멈추는 조건)
        return
    
    print_numbers(n - 1)  # 재귀 호출 (자기 자신 호출)
    print(n)
print_numbers(3)
# 출력:
# 1
# 2
# 3
# 실행 과정:
# print_numbers(3)
#   → print_numbers(2)
#     → print_numbers(1)
#       → print_numbers(0) (멈춤)
#       → print(1)
#     → print(2)
#   → print(3)

트리 구조 이해

백트래킹은 결정 트리(Decision Tree)를 탐색합니다.

예시: [1, 2, 3]에서 2개 선택하기
                    []
          /          |          \
        [1]         [2]         [3]
       /   \         |
    [1,2] [1,3]   [2,3]
각 노드: 현재까지의 선택
각 가지: 다음 선택지
리프 노드: 최종 결과

경우의 수란?

경우의 수는 가능한 모든 경우를 세는 것입니다.

# 예시: [1, 2, 3]을 나열하는 모든 방법
# 순열 (순서 중요, 3! = 6가지)
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
# 조합 (순서 무관, 2개 선택 = 3가지)
[1, 2]
[1, 3]
[2, 3]
# 부분집합 (2³ = 8가지)
[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

백트래킹의 핵심 아이디어

“미로 탈출”을 생각해보세요:

미로 탈출 전략:
1. 한 방향으로 계속 진행
2. 막다른 길이면 → 되돌아가기 (Backtrack)
3. 다른 방향 시도
4. 출구 찾을 때까지 반복
백트래킹도 똑같습니다:
1. 하나의 선택을 함
2. 조건을 만족하지 않으면 → 되돌아가기
3. 다른 선택 시도
4. 해를 찾을 때까지 반복

코드로 표현:

def backtrack(선택들):
    # 1. 해를 찾았으면 저장
    if 조건_만족(선택들):
        결과_저장(선택들)
        return
    
    # 2. 모든 선택지 시도
    for 선택 in 가능한_선택들:
        if 유효한_선택(선택):  # 가지치기!
            선택_추가(선택)      # 선택
            backtrack(선택들)    # 다음 단계로
            선택_제거(선택)      # 되돌리기 (Backtrack)

가지치기(Pruning)란?

가지치기는 불가능한 경우를 미리 제거하는 것입니다.

# 예시: 합이 10인 3개 숫자 조합 찾기 (1~9 사용)
# ❌ 가지치기 없음 (모든 경우 탐색)
def no_pruning(nums, target):
    # [1,2,3], [1,2,4], ..., [7,8,9]
    # 총 84가지 모두 확인 (느림!)
    pass
# ✅ 가지치기 있음 (불가능한 경우 제외)
def with_pruning(nums, current_sum, target):
    # 현재 합이 이미 10을 넘으면 → 더 이상 탐색 안함!
    if current_sum > target:
        return  # 가지치기!
    
    # 예: [1, 2]까지 선택했고 합이 3
    # 다음에 8을 선택하면 합이 11 → 10 초과
    # 8, 9는 탐색할 필요 없음!

가지치기의 효과:

가지치기 없음:
              []
       /      |      \
     [1]    [2]    [3]
    / | \   / | \   / | \
  ...  ...  ...  ...  ...
  (모든 경우 탐색 - 느림)
가지치기 있음:
              []
       /      |      \
     [1]    [2]    [3]
    / | \    |      X (합 초과, 가지치기!)
  ...  X     X
  (불가능한 경우 제외 - 빠름!)

백트래킹 vs 완전 탐색

완전 탐색 (Brute Force):

  • 모든 경우를 다 확인

  • 느리지만 확실함 백트래킹:

  • 조건을 만족하는 경우만 확인

  • 가지치기로 빠름

# 완전 탐색: 모든 3자리 비밀번호 시도 (000~999)
for i in range(1000):
    if try_password(i):
        return i
# 최악: 1000번 시도
# 백트래킹: 조건 활용 (첫 자리가 5라는 힌트)
for i in range(500, 600):  # 500~599만 시도
    if try_password(i):
        return i
# 최악: 100번 시도 (10배 빠름!)

이 비밀번호 예시는 “조건을 먼저 쓰면 탐색 공간이 줄어든다”는 효과를 보여 주는 비유일 뿐, 엄밀한 백트래킹은 아닙니다. 진짜 백트래킹은 답을 한 자리씩 만들어 가다가, 만드는 도중에 “이 앞부분으로는 어떤 답도 나올 수 없다”는 것을 알게 되는 순간 그 아래 전체를 버리는 방식입니다. 그래서 백트래킹의 성능은 얼마나 일찍 실패를 알아챌 수 있는가에 달려 있습니다. N-Queen에서 퀸을 한 줄씩 놓을 때마다 충돌을 검사하면 4번째 줄쯤에서 대부분의 분기가 잘리지만, 8개를 모두 놓은 뒤에 검사하면 8⁸(약 1,677만) 가지를 전부 만들어야 합니다. 같은 문제라도 검사 위치 하나로 탐색량이 수백 배 달라지는 이유입니다.

백트래킹 기본

DFS vs 백트래킹

DFS (깊이 우선 탐색):

  • 연결된 모든 노드를 방문

  • 방문 여부만 체크 백트래킹:

  • 조건을 만족하는 해만 탐색

  • 조건 불만족 시 즉시 되돌아감 (가지치기)

# DFS: 모든 노드 방문
def dfs(node, visited):
    visited.add(node)
    for child in node.children:
        if child not in visited:
            dfs(child, visited)
# 백트래킹: 조건 체크 + 가지치기
def backtrack(state):
    if is_solution(state):
        add_solution(state)
        return
    
    for choice in get_choices(state):
        if is_valid(choice):  # 가지치기!
            make_choice(choice)
            backtrack(state)
            undo_choice(choice)  # 되돌리기

백트래킹 템플릿

def backtrack_template(state, choices, result):
    """
    백트래킹 범용 템플릿
    """
    # 1. 종료 조건
    if is_complete(state):
        result.append(state.copy())
        return
    
    # 2. 가지치기 (조기 종료)
    if not is_valid(state):
        return
    
    # 3. 선택 시도
    for choice in choices:
        # 선택
        state.add(choice)
        
        # 재귀
        backtrack_template(state, choices, result)
        
        # 되돌리기
        state.remove(choice)

템플릿의 핵심은 하나의 상태 객체를 계속 고쳐 쓰고 되돌린다는 점입니다. 재귀 호출마다 state + [choice]처럼 새 리스트를 만들어 넘기면 되돌리기가 필요 없어 코드는 단순해지지만, 호출마다 복사 비용이 들어 깊이가 깊어지면 느려집니다. 반대로 공유 상태를 쓰면 빠르지만 되돌리기를 하나라도 빠뜨리면 이후 모든 분기가 오염됩니다. “선택한 것은 반드시 같은 들여쓰기 수준에서 되돌린다”는 대칭을 지키는 것이 이 방식의 유일한 규칙입니다. 종료 조건에서 state.copy()로 복사본을 저장하는 이유도 같습니다. 저장한 것이 참조라면 되돌리기가 끝났을 때 결과 리스트의 모든 원소가 같은 빈 상태를 가리키게 됩니다.

순열과 조합

순열 (Permutation)

정의: n개 중 r개를 순서를 고려하여 선택 예시: [1, 2, 3]에서 2개 선택 → [1,2], [1,3], [2,1], [2,3], [3,1], [3,2]

Python 구현

def permutations(arr, n):
    """
    순열: nPr
    - 순서 O, 중복 X
    - 시간: O(n!)
    """
    result = []
    
    def backtrack(path, remaining):
        if len(path) == n:
            result.append(path[:])
            return
        
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    
    backtrack([], arr)
    return result
# 테스트
print(permutations([1, 2, 3], 2))
# [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

C++ 구현

#include <vector>
#include <iostream>
using namespace std;
void permutationsHelper(
    vector<int>& arr, 
    int n, 
    vector<int>& path, 
    vector<bool>& used, 
    vector<vector<int>>& result
) {
    if (path.size() == n) {
        result.push_back(path);
        return;
    }
    
    for (int i = 0; i < arr.size(); ++i) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(arr[i]);
            
            permutationsHelper(arr, n, path, used, result);
            
            path.pop_back();
            used[i] = false;
        }
    }
}
vector<vector<int>> permutations(vector<int>& arr, int n) {
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used(arr.size(), false);
    
    permutationsHelper(arr, n, path, used, result);
    return result;
}
int main() {
    vector<int> arr = {1, 2, 3};
    auto result = permutations(arr, 2);
    
    for (const auto& perm : result) {
        for (int num : perm) {
            cout << num << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

시간 복잡도: O(n!)
공간 복잡도: O(n)

정확히는 n개 중 r개를 고르는 순열의 개수가 n!/(n−r)!이고, 각 결과를 복사하는 데 O(r)이 드므로 전체는 O(r × n!/(n−r)!)입니다. 결과 개수 자체가 이만큼이라 어떤 알고리즘으로도 이보다 빨리 모든 순열을 나열할 수는 없습니다. Python 구현은 매 호출마다 remaining[:i] + remaining[i+1:]로 새 리스트를 만들어 이해하기 쉽지만, C++ 구현처럼 used 배열로 사용 여부를 표시하면 복사가 없어 더 빠릅니다. 실무나 코딩 테스트에서 순열 자체가 필요하다면 Python의 itertools.permutations, C++의 std::next_permutation(정렬된 상태에서 시작해야 모든 순열이 나옴)이 이미 최적화되어 있으므로 직접 구현할 이유가 거의 없고, 직접 짜는 것은 중간에 가지치기를 끼워 넣어야 할 때입니다.

조합 (Combination)

정의: n개 중 r개를 순서 무관하게 선택 예시: [1, 2, 3]에서 2개 선택 → [1,2], [1,3], [2,3]

Python 구현

def combinations(arr, n):
    """
    조합: nCr
    - 순서 X, 중복 X
    - 시간: O(2ⁿ)
    """
    result = []
    
    def backtrack(start, path):
        if len(path) == n:
            result.append(path[:])
            return
        
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result
# 테스트
print(combinations([1, 2, 3], 2))
# [[1, 2], [1, 3], [2, 3]]

C++ 구현

#include <vector>
#include <iostream>
using namespace std;
void combinationsHelper(
    const vector<int>& arr, 
    int n, 
    int start, 
    vector<int>& path, 
    vector<vector<int>>& result
) {
    if (path.size() == n) {
        result.push_back(path);
        return;
    }
    
    for (int i = start; i < arr.size(); ++i) {
        path.push_back(arr[i]);
        combinationsHelper(arr, n, i + 1, path, result);
        path.pop_back();
    }
}
vector<vector<int>> combinations(const vector<int>& arr, int n) {
    vector<vector<int>> result;
    vector<int> path;
    
    combinationsHelper(arr, n, 0, path, result);
    return result;
}
int main() {
    vector<int> arr = {1, 2, 3};
    auto result = combinations(arr, 2);
    
    for (const auto& comb : result) {
        for (int num : comb) {
            cout << num << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

시간 복잡도: O(2ⁿ)
공간 복잡도: O(n)

O(2ⁿ)는 가능한 모든 부분집합 수에 해당하는 상한이고, r개를 고르는 조합의 개수는 정확히 C(n, r)입니다. 순열과의 차이는 재귀에 넘기는 i + 1 하나뿐입니다. “지금 고른 원소보다 뒤에 있는 원소만 다음 후보로 삼는다”는 규칙이 [1, 2]와 [2, 1]을 같은 것으로 만들어 줍니다. 여기에 가지치기를 하나 더 넣을 수 있습니다. 남은 원소 수가 더 골라야 할 수보다 적으면(len(arr) - i < n - len(path)) 그 분기에서는 절대 r개를 채울 수 없으므로 루프를 끝내도 됩니다. n이 크고 r이 n에 가까울 때 이 조건 하나로 탐색량이 크게 줄어듭니다.

부분집합 (Subset)

정의: 모든 가능한 부분집합 생성

Python 구현

def subsets(arr):
    """
    모든 부분집합
    - 시간: O(2ⁿ)
    """
    result = []
    
    def backtrack(start, path):
        result.append(path[:])
        
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result
# 테스트
print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

N-Queen 문제

문제 설명

N×N 체스판에 N개의 퀸을 배치하되, 서로 공격할 수 없도록 배치합니다.

제약:

  • 같은 행에 퀸 없음
  • 같은 열에 퀸 없음
  • 같은 대각선에 퀸 없음

Python 구현

def solve_n_queens(n):
    """
    N-Queen 문제
    - 백트래킹으로 모든 해 찾기
    """
    result = []
    board = [['.'] * n for _ in range(n)]
    
    def is_valid(row, col):
        # 같은 열 체크
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # 왼쪽 위 대각선
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        
        # 오른쪽 위 대각선
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        
        return True
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if is_valid(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
    
    backtrack(0)
    return result
# 테스트
solutions = solve_n_queens(4)
print(f"{len(solutions)}개 해")
for i, sol in enumerate(solutions):
    print(f"\n해 {i + 1}:")
    for row in sol:
        print(row)
# 출력:
# 2개 해
# 
# 해 1:
# .Q..
# ...Q
# Q...
# ..Q.
# 
# 해 2:
# ..Q.
# Q...
# ...Q
# .Q..

최적화 버전 (Set 사용)

def solve_n_queens_optimized(n):
    """
    N-Queen 최적화
    - Set으로 O(1) 충돌 체크
    """
    result = []
    board = [['.'] * n for _ in range(n)]
    
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            
            backtrack(row + 1)
            
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    backtrack(0)
    return result
# 테스트
solutions = solve_n_queens_optimized(8)
print(f"8-Queen: {len(solutions)}개 해")  # 92개

시간 복잡도: O(n!) — 가지치기로 실제는 훨씬 빠름

두 구현의 차이는 충돌 검사 비용입니다. 첫 번째 버전은 퀸을 놓을 때마다 위쪽 행들을 훑어 O(n)이 들고, 최적화 버전은 “이 열에 퀸이 있는가”, “이 대각선에 퀸이 있는가”를 집합으로 O(1)에 답합니다. 대각선을 row - col과 row + col로 표현할 수 있는 이유는, 왼쪽 위에서 오른쪽 아래로 가는 대각선 위의 칸은 모두 row - col 값이 같고, 반대 방향 대각선의 칸은 row + col 값이 같기 때문입니다. 행은 한 줄에 하나씩 놓으므로 애초에 검사할 필요가 없습니다. 탐색 구조 자체를 “행마다 하나”로 설계해 제약 하나를 없앤 것으로, 제약을 검사하는 것보다 제약이 성립할 수밖에 없게 상태를 설계하는 것이 더 강력한 가지치기라는 점을 보여 줍니다.

n이 커지면 해의 개수도 폭발적으로 늘어납니다(8에서 92개, 12에서 14,200개). 해를 모두 문자열 보드로 저장하면 메모리가 먼저 문제가 되므로, 개수만 필요한 문제(LeetCode 52, 백준 9663)에서는 보드를 만들지 말고 카운터만 올려야 합니다. 더 빠르게 하려면 세 집합을 정수 비트마스크로 바꾸는 방법이 흔히 쓰입니다.

고급 활용

부분집합 합 (Subset Sum)

문제: 합이 target인 부분집합 찾기

Python 구현

def subset_sum(arr, target):
    """
    부분집합 합 문제
    - 가지치기: current_sum > target
    """
    result = []
    
    def backtrack(start, path, current_sum):
        if current_sum == target:
            result.append(path[:])
            return
        
        if current_sum > target:
            return
        
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, path, current_sum + arr[i])
            path.pop()
    
    backtrack(0, [], 0)
    return result
# 테스트
arr = [1, 2, 3, 4, 5]
target = 5
print(subset_sum(arr, target))
# [[1, 4], [2, 3], [5]]

current_sum > target에서 멈추는 가지치기는 모든 원소가 양수일 때만 올바릅니다. 음수가 섞여 있으면 합이 target을 넘었다가 뒤의 음수로 다시 내려올 수 있어서, 이 조건이 정답을 잘라 버립니다. 문제 조건에 “양의 정수”가 명시되어 있는지 먼저 확인해야 하고, 그렇지 않다면 이 가지치기를 빼거나 남은 원소 중 음수의 합으로 하한을 계산하는 식으로 바꿔야 합니다. 합이 target과 같아진 순간 return하는 것도 양수라는 전제에 기대고 있습니다. 0이 원소로 들어 있다면 [5]와 [5, 0]이 모두 답이어야 하는데, 이 코드는 [5]에서 멈추므로 [5, 0]을 놓칩니다.

조합 합 (Combination Sum)

문제: LeetCode 39 - Combination Sum 특징: 같은 숫자를 여러 번 사용 가능

Python 구현

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []
        
        def backtrack(start, path, current_sum):
            if current_sum == target:
                result.append(path[:])
                return
            
            if current_sum > target:
                return
            
            for i in range(start, len(candidates)):
                path.append(candidates[i])
                backtrack(i, path, current_sum + candidates[i])
                path.pop()
        
        backtrack(0, [], 0)
        return result
# 테스트
sol = Solution()
print(sol.combinationSum([2, 3, 6, 7], 7))
# [[2, 2, 3], [7]]

앞의 부분집합 합과 비교하면 재귀 호출의 인자가 i + 1이 아니라 i라는 점 하나만 다릅니다. 같은 원소를 다시 고를 수 있게 하되, 앞의 원소로는 돌아가지 않으므로 [2, 2, 3]과 [2, 3, 2]가 중복으로 나오지 않습니다. 이 한 글자 차이로 “중복 사용 불가 조합”, “중복 사용 가능 조합”, “순열”이 갈리므로, 문제를 읽을 때 “같은 원소를 여러 번 쓸 수 있는가”와 “순서가 다르면 다른 답인가” 두 질문에 먼저 답하면 어떤 틀을 써야 할지 정해집니다.

입력 배열 자체에 같은 값이 여러 번 들어 있는 경우(LeetCode 40, 90)는 또 다릅니다. [1, 1, 2]에서 두 개를 고르면 첫 번째 1을 쓴 [1, 2]와 두 번째 1을 쓴 [1, 2]가 따로 나옵니다. 입력을 정렬한 뒤 루프 안에서 if i > start and arr[i] == arr[i - 1]: continue로 같은 깊이에서 같은 값은 한 번만 시도하게 하면 결과를 set으로 걸러 내지 않고도 중복이 사라집니다. 결과를 set(tuple(...))로 거르는 방법은 동작은 하지만 중복된 분기를 모두 탐색한 뒤에 버리므로 입력이 커지면 시간 초과가 납니다.

스도쿠 (Sudoku)

문제: LeetCode 37 - Sudoku Solver

Python 구현

def solve_sudoku(board):
    """
    9x9 스도쿠 풀기
    """
    def is_valid(row, col, num):
        # 행 체크
        if num in board[row]:
            return False
        
        # 열 체크
        if num in [board[i][col] for i in range(9)]:
            return False
        
        # 3x3 박스 체크
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False
        
        return True
    
    def backtrack():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(i, j, num):
                            board[i][j] = num
                            
                            if backtrack():
                                return True
                            
                            board[i][j] = '.'
                    
                    return False
        return True
    
    backtrack()
    return board
# 테스트
board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
solve_sudoku(board)
for row in board:
    print(' '.join(row))

이 스도쿠 풀이에서 가장 헷갈리는 부분은 return False의 위치입니다. 빈 칸 하나에 1~9를 모두 넣어 봐도 안 되면, 그 칸에 들어갈 값이 없다는 뜻이므로 바로 이전 선택이 틀렸다는 신호입니다. 그래서 두 개의 for 루프를 끝까지 돌지 않고 첫 번째 빈 칸에서 False를 돌려 호출한 쪽이 다른 숫자를 시도하게 합니다. 이 줄을 루프 밖으로 옮기면 빈 칸을 건너뛰고 다음 칸으로 넘어가 버려 틀린 보드가 “풀렸다”고 반환됩니다.

성능 측면에서는 is_valid가 호출될 때마다 열 전체를 리스트로 새로 만들고 3×3 박스를 훑는 것이 병목입니다. 행·열·박스마다 사용 중인 숫자를 집합이나 비트마스크로 유지하면 검사가 O(1)이 됩니다. 또 빈 칸을 왼쪽 위부터 순서대로 채우는 대신 후보 숫자가 가장 적은 칸부터 채우면(MRV 휴리스틱) 잘못된 선택이 훨씬 일찍 드러나 어려운 퍼즐에서 탐색량이 크게 줄어듭니다. 제약 만족 문제에서 “가장 제약이 강한 변수부터 정한다”는 이 원칙은 스도쿠뿐 아니라 일정 배정이나 자원 할당 같은 실무 문제에도 그대로 적용됩니다.

문제: LeetCode 79 - Word Search

Python 구현

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        
        def backtrack(r, c, idx):
            if idx == len(word):
                return True
            
            if (r < 0 or r >= rows or c < 0 or c >= cols or 
                board[r][c] != word[idx]):
                return False
            
            temp = board[r][c]
            board[r][c] = '#'
            
            found = (backtrack(r + 1, c, idx + 1) or
                    backtrack(r - 1, c, idx + 1) or
                    backtrack(r, c + 1, idx + 1) or
                    backtrack(r, c - 1, idx + 1))
            
            board[r][c] = temp
            return found
        
        for i in range(rows):
            for j in range(cols):
                if backtrack(i, j, 0):
                    return True
        
        return False
# 테스트
sol = Solution()
board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]
print(sol.exist(board, "ABCCED"))  # True
print(sol.exist(board, "SEE"))     # True
print(sol.exist(board, "ABCB"))    # False

단어 검색은 방문 표시를 별도 visited 집합 대신 보드 칸을 잠시 '#'로 바꾸는 방식으로 처리합니다. 추가 메모리가 필요 없고 검사도 빠르지만, 탐색이 끝난 뒤 board[r][c] = temp로 원래 글자를 되돌리지 않으면 다음 시작점에서 보드가 망가진 상태로 탐색하게 됩니다. found를 or로 연결한 것도 의미가 있습니다. 한 방향에서 단어를 찾으면 나머지 방향은 평가하지 않는 단락 평가 덕분에 첫 해를 찾는 즉시 멈춥니다. LeetCode에서 이 문제의 큰 테스트 케이스를 통과하려면, 보드에 있는 글자 수가 단어에 필요한 글자 수보다 적으면 탐색 전에 False를 돌려주는 식의 사전 검사를 추가하는 경우가 많습니다.

실무 사례

사례 1: 작업 스케줄링 - 제약 만족

시나리오: 작업 시간과 의존성 제약을 만족하는 스케줄 찾기

Python 구현

from dataclasses import dataclass
@dataclass
class Task:
    id: int
    duration: int
    dependencies: list[int]
def schedule_tasks(tasks, max_time):
    """
    제약 만족 스케줄링
    """
    n = len(tasks)
    result = []
    
    def is_valid(schedule, task_idx):
        task = tasks[task_idx]
        
        for dep_id in task.dependencies:
            if dep_id not in schedule:
                return False
        
        current_time = sum(tasks[i].duration for i in schedule)
        if current_time + task.duration > max_time:
            return False
        
        return True
    
    def backtrack(schedule):
        if len(schedule) == n:
            result.append(schedule[:])
            return
        
        for i in range(n):
            if i not in schedule and is_valid(schedule, i):
                schedule.append(i)
                backtrack(schedule)
                schedule.pop()
    
    backtrack([])
    return result
# 테스트
tasks = [
    Task(0, 2, []),
    Task(1, 3, [0]),
    Task(2, 1, [0]),
    Task(3, 2, [1, 2]),
]
schedules = schedule_tasks(tasks, 10)
print(f"{len(schedules)}개 가능한 스케줄")
for schedule in schedules:
    print([tasks[i].id for i in schedule])

이 예제는 백트래킹으로 가능한 모든 실행 순서를 나열합니다. 의존성만 만족하는 순서 하나가 필요하다면 위상 정렬(Kahn 알고리즘)이 O(V + E)로 끝나므로 백트래킹을 쓸 이유가 없습니다. 작업 수가 10개만 넘어가도 가능한 순서가 수백만 개가 될 수 있기 때문입니다. 백트래킹이 의미를 갖는 것은 “작업자 두 명이 동시에 일할 때 전체 완료 시간이 가장 짧은 배정”처럼 순서마다 비용이 달라 모두 비교해야 하고, 효율적인 공식 알고리즘이 없는 경우입니다. 또 이 코드는 Task.id와 리스트 인덱스가 같다고 가정하고 dependencies에 인덱스를 적고 있으므로, id를 임의로 매기면 의존성 검사가 틀어진다는 점도 알아 둘 만합니다.

사례 2: 조합 최적화 - 배낭 문제

시나리오: 무게 제한 내에서 가치 최대화

Python 구현

def knapsack_backtrack(items, capacity):
    """
    0-1 배낭 문제 (백트래킹)
    - items: [(weight, value), ...]
    """
    best_value = [0]
    best_items = []
    
    def backtrack(idx, current_weight, current_value, path):
        if current_value > best_value[0]:
            best_value[0] = current_value
            best_items.clear()
            best_items.extend(path)
        
        if idx == len(items):
            return
        
        weight, value = items[idx]
        
        if current_weight + weight <= capacity:
            path.append(idx)
            backtrack(idx + 1, current_weight + weight, current_value + value, path)
            path.pop()
        
        backtrack(idx + 1, current_weight, current_value, path)
    
    backtrack(0, 0, 0, [])
    return best_value[0], best_items
# 테스트
items = [(2, 3), (3, 4), (4, 5), (5, 6)]
capacity = 8
max_value, selected = knapsack_backtrack(items, capacity)
print(f"최대 가치: {max_value}")
print(f"선택한 아이템: {selected}")
# 최대 가치: 10
# 선택한 아이템: [1, 3] (무게 3+5=8, 가치 4+6=10)

무게 제한 8 안에서 가능한 조합을 모두 따져보면 항목 1과 3(무게 3+5=8, 가치 4+6=10)이 실제 최적해입니다. current_value > best_value[0]일 때마다 갱신하는 방식이라, 탐색 순서에 따라 중간에 갱신되었다가 더 나은 조합이 나오면 다시 덮어써지는 과정을 거쳐 최종적으로 이 조합에 도달합니다.

이 구현의 가지치기는 “무게를 넘으면 넣지 않는다” 하나뿐이라, 사실상 2ⁿ 가지를 거의 다 봅니다. 최적화 문제에서 백트래킹을 쓸 만하게 만드는 것은 상한(bound)을 이용한 가지치기, 즉 분기 한정(branch and bound)입니다. 남은 물건을 가치/무게 비율 순으로 쪼개 넣을 수 있다고 가정하고 계산한 가치(분할 배낭 상한)가 지금까지 찾은 최선보다 작다면, 그 분기는 끝까지 가 봐야 최선을 넘을 수 없으므로 버립니다. 다만 무게가 정수이고 용량이 크지 않다면 O(n × capacity) DP가 훨씬 단순하고 빠르므로, 백트래킹 배낭은 용량이 매우 크거나 무게가 실수인 경우에 고려하는 방법입니다.

사례 3: 경로 탐색 - 미로 탈출

시나리오: 미로에서 모든 가능한 경로 찾기

Python 구현

def find_all_paths(maze, start, end):
    """
    미로 모든 경로 찾기
    - 0: 통행 가능, 1: 벽
    """
    rows, cols = len(maze), len(maze[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    result = []
    
    def backtrack(r, c, path, visited):
        if (r, c) == end:
            result.append(path[:])
            return
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if (0 <= nr < rows and 0 <= nc < cols and 
                maze[nr][nc] == 0 and (nr, nc) not in visited):
                
                visited.add((nr, nc))
                path.append((nr, nc))
                
                backtrack(nr, nc, path, visited)
                
                path.pop()
                visited.remove((nr, nc))
    
    visited = {start}
    backtrack(start[0], start[1], [start], visited)
    return result
# 테스트
maze = [
    [0, 0, 1],
    [0, 0, 0],
    [1, 0, 0]
]
start = (0, 0)
end = (2, 2)
paths = find_all_paths(maze, start, end)
print(f"{len(paths)}개 경로")
for path in paths:
    print(path)

트러블슈팅

문제 1: 되돌리기 누락

증상: 상태가 복구되지 않아 잘못된 결과

# 잘못된 예
def backtrack_wrong(path):
    if len(path) == n:
        result.append(path)  # path 참조 저장
        return
    
    for choice in choices:
        path.append(choice)
        backtrack_wrong(path)
        # path.pop() 누락!

이 잘못된 예에는 버그가 두 개 겹쳐 있습니다. pop()이 없으면 path가 계속 길어져 첫 해를 찾은 뒤로는 길이 조건을 다시 만족하지 못하고 재귀가 끝없이 깊어지다가 RecursionError로 멈춥니다. 그리고 result.append(path)는 복사본이 아니라 같은 리스트를 저장하므로, 설령 pop()을 고쳐도 탐색이 끝났을 때 결과가 [[], [], [], ...]처럼 전부 빈 리스트로 보입니다. 둘 중 하나만 고치면 증상이 바뀌기만 하고 여전히 틀리기 때문에, 디버깅할 때 헷갈리기 쉬운 조합입니다. 해결:

def backtrack_correct(path):
    if len(path) == n:
        result.append(path[:])  # 복사본 저장
        return
    
    for choice in choices:
        path.append(choice)
        backtrack_correct(path)
        path.pop()  # 되돌리기

문제 2: 가지치기 누락

증상: 불필요한 탐색으로 시간 초과

# 가지치기 없음
def backtrack_slow(current_sum, path):
    if len(path) == n:
        if current_sum == target:
            result.append(path[:])
        return
    
    for num in arr:
        path.append(num)
        backtrack_slow(current_sum + num, path)
        path.pop()

해결: 조기 종료 추가

def backtrack_fast(start, current_sum, path):
    if current_sum == target:
        result.append(path[:])
        return
    
    if current_sum > target:  # 가지치기!
        return
    
    for i in range(start, len(arr)):
        path.append(arr[i])
        backtrack_fast(i + 1, current_sum + arr[i], path)
        path.pop()

문제 3: 중복 결과

증상: 같은 조합이 여러 번 나옴

# 잘못된 예
def combinations_wrong(arr, n):
    result = []
    
    def backtrack(path):
        if len(path) == n:
            result.append(path[:])
            return
        
        for num in arr:  # start 없음
            path.append(num)
            backtrack(path)
            path.pop()
    
    backtrack([])
    return result
# [1,2,3], n=2 → [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]
# 중복: [1,2]와 [2,1]

해결: start 인덱스 추가

def combinations_correct(arr, n):
    result = []
    
    def backtrack(start, path):
        if len(path) == n:
            result.append(path[:])
            return
        
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

문제 4: 시간 초과 (TLE)

증상: n이 커지면 지수 시간 복잡도로 시간 초과 해결 1: 가지치기 강화

# 정렬 후 조기 종료
arr.sort()
def backtrack(start, current_sum, path):
    if current_sum == target:
        result.append(path[:])
        return
    
    for i in range(start, len(arr)):
        if current_sum + arr[i] > target:
            break  # 정렬되어 있으므로 이후는 불필요
        
        path.append(arr[i])
        backtrack(i + 1, current_sum + arr[i], path)
        path.pop()

해결 2: DP로 전환

# 부분집합 합은 DP로도 해결 가능
def subset_sum_dp(arr, target):
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in arr:
        for i in range(target, num - 1, -1):
            if dp[i - num]:
                dp[i] = True
    
    return dp[target]

마무리

백트래킹은 모든 경우의 수를 탐색하되, 가지치기로 불필요한 탐색을 건너뛰는 알고리즘입니다.

핵심 패턴

def backtrack(state):
    # 1. 종료 조건
    if is_complete(state):
        save_solution(state)
        return
    
    # 2. 가지치기
    if not is_valid(state):
        return
    
    # 3. 선택 → 재귀 → 되돌리기
    for choice in get_choices():
        make_choice(choice)
        backtrack(new_state)
        undo_choice(choice)

시간 복잡도

문제시간 복잡도가지치기 효과
순열O(n!)낮음
조합O(2ⁿ)중간
부분집합 합O(2ⁿ)높음 (정렬 시)
N-QueenO(n!)매우 높음
스도쿠O(9^m)매우 높음 (m은 빈 칸)

선택 가이드

문제 유형알고리즘
모든 순열백트래킹
모든 조합백트래킹
최적 부분집합DP (가능하면)
제약 만족백트래킹

추천 문제

백준:

다음 단계

같이 보면 좋은 글