백트래킹과 가지치기 전략 설계

백트래킹은 가능한 경우를 탐색하되 불필요한 분기를 미리 자르는 방식입니다. 처음에는 모든 경우를 다 돌려도 될 것 같지만 입력이 커지면 바로 시간 초과가 납니다. 그래서 가지치기 조건을 정확히 세우는 것이 중요합니다.

가지치기를 잘못 넣으면 정답 경로까지 잘라서 오답이 됩니다. 여기서는 재귀 문법보다 상태 표현, 후보 생성, 가지치기 결정 배경를 우선 고정하는 흐름을 강조합니다. 조건 과잉/조건 누락처럼 자주 틀리는 지점도 함께 정리합니다.

핵심 원리 청사진: 백트래킹 가지치기

백트래킹의 상태-가지치기-복원 흐름 다이어그램

가지치기 안전성 체크맵

가지치기 조건을 작성할 때 안전성 점검 순서를 먼저 고정하면 오답 가지치기를 줄일 수 있습니다. 아래 체크맵은 정답 경로 보존과 탐색 축소를 함께 판단하는 기준선을 보여줍니다.

백트래킹은 후보를 모두 보되, 볼 필요 없는 분기를 빨리 끊는 설계가 핵심입니다. 코드를 쓰기 전에 가지치기 결정 배경를 문장으로 우선 적어 두세요.

상태(state)는 현재까지 선택한 결과를 표현하는 정보 집합입니다. 탐색 트리에서 현재 노드를 식별하고, 다음 후보 생성과 종료 판정을 가능하게 만드는 기준입니다. N-Queen에서는 현재 행 번호와 열/대각선 사용 여부가 대표적인 상태가 됩니다.

가지치기(pruning)는 정답 가능성이 사라진 분기를 미리 중단하는 규칙입니다. 현재 부분해가 제약을 위반하거나 최적해로 이어질 수 없을 때 하위 탐색을 생략합니다. 모든 수가 양수인 부분합 문제에서 현재 합이 목표를 넘으면 그 아래 분기는 더 볼 필요가 없습니다.

상태 복원(backtrack)은 재귀 호출 후 바꾼 상태를 원래로 되돌리는 절차입니다. 형제 분기 간 독립성을 유지하려면 호출 전에 바꾼 값을 호출 후 반드시 복구해야 합니다. 후보를 집합에 추가하고 재귀 호출한 뒤, 다음 후보 탐색 전에 같은 원소를 제거하는 패턴이 기본입니다.

백트래킹 가지치기가 운영에 미치는 영향

완전 탐색은 정답 보장은 강하지만 입력이 커지면 즉시 폭발합니다. 가지치기 설계를 잘하면 같은 문제도 탐색 노드 수가 수십 배 이상 줄어들 수 있습니다.

반대로 가지치기 조건이 잘못되면 정답 분기까지 잘라내어 치명적인 오답이 됩니다. 정확성과 성능을 함께 보는 설계가 필요합니다.

가지치기 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

부분집합 탐색에서 가지치기 흐름을 간단히 확인합니다.

숫자: [7,3,2,5,8]
목표 합: 14

현재 합이 목표를 초과하면 해당 분기를 중단합니다.
남은 수를 모두 더해도 목표에 못 미치면 중단합니다.
포함/미포함 분기를 재귀로 전개해 가능한 조합만 탐색합니다.
가지치기 조건이 틀리면 정답 분기를 잘라낼 수 있으니 결정 배경가 필요합니다.

가지치기 기반 백트래킹 적용 관찰점

아래 신호가 있으면 백트래킹 후보입니다.

후보 공간이 유한하고 명시적으로 생성 가능하다.
부분 상태에서 불가능 판정 조건을 만들 수 있다.
해를 하나 또는 일부만 찾아도 된다.
DP 상태화가 과도하게 커진다.

상태 중복이 많다면 백트래킹 단독보다 DP/메모이제이션 병합을 고려하세요.

백트래킹: 부분집합 합 존재 여부

문제 의도: 포함/미포함 분기와 가지치기로 부분집합 합 존재 여부를 판정합니다.
입력 예시: nums=[7,3,2,5,8], target=14
출력 예시: true

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool dfsSubset(const vector<int>& nums, int target, int idx, int current) {
    if (current == target) {
        return true;
    }
    if (idx == (int)nums.size()) {
        return false;
    }
    if (current > target) {
        return false; // 양수 배열 전제 가지치기
    }
    if (dfsSubset(nums, target, idx + 1, current + nums[idx])) {
        return true;
    }
    return dfsSubset(nums, target, idx + 1, current);
}

bool subsetSumExists(vector<int> nums, int target) {
    sort(nums.rbegin(), nums.rend());
    return dfsSubset(nums, target, 0, 0);
}

int main() {
    cout << subsetSumExists({7, 3, 2, 5, 8}, 14) << "\n";
    return 0;
}

Main.java

import java.util.Arrays;

public class Main {
    static boolean found;
    static int[] nums;
    static int target;

    static void dfs(int idx, int current) {
        if (found) return;
        if (current == target) {
            found = true;
            return;
        }
        if (idx == nums.length) return;
        if (current > target) return; // 양수 배열 전제 가지치기

        dfs(idx + 1, current + nums[idx]); // 포함
        dfs(idx + 1, current);             // 미포함
    }

    static boolean subsetSumExists(int[] arr, int t) {
        nums = arr.clone();
        target = t;
        Arrays.sort(nums);
        for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
            int x = nums[i]; nums[i] = nums[j]; nums[j] = x;
        }
        found = false;
        dfs(0, 0);
        return found;
    }

    public static void main(String[] args) {
        System.out.println(subsetSumExists(new int[]{7, 3, 2, 5, 8}, 14));
    }
}

main.py

def dfs_subset(nums, target, idx, current):
    if current == target:
        return True
    if idx == len(nums):
        return False
    if current > target:  # 양수 배열 전제 가지치기
        return False
    if dfs_subset(nums, target, idx + 1, current + nums[idx]):
        return True
    return dfs_subset(nums, target, idx + 1, current)

def subset_sum_exists(nums, target):
    nums.sort(reverse=True)
    return dfs_subset(nums, target, 0, 0)

print(subset_sum_exists([7, 3, 2, 5, 8], 14))
# 출력: True

main.rs

fn subset_sum_exists(mut nums: Vec<i32>, target: i32) -> bool {
    nums.sort();
    nums.reverse();
    fn dfs(idx: usize, current: i32, nums: &[i32], target: i32, found: &mut bool) {
        if *found {
            return;
        }
        if current == target {
            *found = true;
            return;
        }
        if idx == nums.len() {
            return;
        }
        if current > target {
            return;
        }
        dfs(idx + 1, current + nums[idx], nums, target, found);
        dfs(idx + 1, current, nums, target, found);
    }

    let mut found = false;
    dfs(0, 0, &nums, target, &mut found);
    found
}

fn main() {
    println!("{}", subset_sum_exists(vec![7, 3, 2, 5, 8], 14));
}

포함/미포함 분기 선정 배경

이 예제는 포함/미포함 두 분기를 가장 단순한 형태로 보여줍니다. current > target 가지치기는 모든 수가 양수라는 전제가 있을 때만 안전합니다. 더 강한 가지치기(예: 접미 합)는 성능을 더 올릴 수 있지만, 우선 기본 분기 구조를 안정적으로 익히는 것이 중요합니다.

평균 시간복잡도: 입력 구조 의존
최악 시간복잡도: O(2^N)
공간복잡도: 재귀 스택 O(N)

백트래킹: N-Queen

문제 의도: 충돌 조건(열/대각선)을 상태로 관리해 탐색 공간을 줄입니다.
입력 예시: n=4
출력 예시: 해 개수와 배치 예시

main.cpp

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

void dfsNQueens(
    int n,
    int r,
    unordered_set<int>& cols,
    unordered_set<int>& diag1,
    unordered_set<int>& diag2,
    vector<int>& board,
    vector<vector<int>>& result
) {
    if (r == n) {
        result.push_back(board);
        return;
    }
    for (int c = 0; c < n; ++c) {
        if (cols.count(c) || diag1.count(r - c) || diag2.count(r + c)) continue;
        board[r] = c;
        cols.insert(c);
        diag1.insert(r - c);
        diag2.insert(r + c);
        dfsNQueens(n, r + 1, cols, diag1, diag2, board, result);
        cols.erase(c);
        diag1.erase(r - c);
        diag2.erase(r + c);
        board[r] = -1;
    }
}

vector<vector<int>> solveNQueens(int n) {
    unordered_set<int> cols, diag1, diag2;
    vector<int> board(n, -1);
    vector<vector<int>> result;
    dfsNQueens(n, 0, cols, diag1, diag2, board, result);
    return result;
}

int main() {
    auto sol = solveNQueens(4);
    cout << sol.size() << " ";
    for (int x : sol[0]) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static List<int[]> solveNQueens(int n) {
        Set<Integer> cols = new HashSet<>();
        Set<Integer> diag1 = new HashSet<>();
        Set<Integer> diag2 = new HashSet<>();
        int[] board = new int[n];
        Arrays.fill(board, -1);
        List<int[]> result = new ArrayList<>();

        class Solver {
            void dfs(int r) {
                if (r == n) {
                    result.add(board.clone());
                    return;
                }
                for (int c = 0; c < n; c++) {
                    if (cols.contains(c) || diag1.contains(r - c) || diag2.contains(r + c)) continue;
                    board[r] = c;
                    cols.add(c);
                    diag1.add(r - c);
                    diag2.add(r + c);
                    dfs(r + 1);
                    cols.remove(c);
                    diag1.remove(r - c);
                    diag2.remove(r + c);
                    board[r] = -1;
                }
            }
        }

        new Solver().dfs(0);
        return result;
    }

    public static void main(String[] args) {
        List<int[]> sol = solveNQueens(4);
        System.out.print(sol.size() + " ");
        System.out.println(Arrays.toString(sol.get(0)));
    }
}

main.py

def solve_n_queens(n):
    cols = set()
    diag1 = set()  # r - c
    diag2 = set()  # r + c
    board = [-1] * n
    result = []

    def dfs(r):
        if r == n:
            result.append(board[:])
            return

        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue

            board[r] = c
            cols.add(c)
            diag1.add(r - c)
            diag2.add(r + c)

            dfs(r + 1)

            cols.remove(c)
            diag1.remove(r - c)
            diag2.remove(r + c)
            board[r] = -1

    dfs(0)
    return result

sol = solve_n_queens(4)
print(len(sol), sol[0])
# 출력 예시: 2 [1, 3, 0, 2]

main.rs

use std::collections::HashSet;

fn solve_n_queens(n: usize) -> Vec<Vec<i32>> {
    let mut cols = HashSet::new();
    let mut diag1 = HashSet::new();
    let mut diag2 = HashSet::new();
    let mut board = vec![-1_i32; n];
    let mut result = Vec::new();

    fn dfs(
        r: usize,
        n: usize,
        cols: &mut HashSet<i32>,
        diag1: &mut HashSet<i32>,
        diag2: &mut HashSet<i32>,
        board: &mut Vec<i32>,
        result: &mut Vec<Vec<i32>>,
    ) {
        if r == n {
            result.push(board.clone());
            return;
        }
        for c in 0..n {
            let rr = r as i32;
            let cc = c as i32;
            if cols.contains(&cc) || diag1.contains(&(rr - cc)) || diag2.contains(&(rr + cc)) {
                continue;
            }
            board[r] = cc;
            cols.insert(cc);
            diag1.insert(rr - cc);
            diag2.insert(rr + cc);
            dfs(r + 1, n, cols, diag1, diag2, board, result);
            cols.remove(&cc);
            diag1.remove(&(rr - cc));
            diag2.remove(&(rr + cc));
            board[r] = -1;
        }
    }

    dfs(0, n, &mut cols, &mut diag1, &mut diag2, &mut board, &mut result);
    result
}

fn main() {
    let sol = solve_n_queens(4);
    println!("{} {:?}", sol.len(), sol[0]);
}

충돌 제약 우선 선정 배경

열/대각선 충돌을 집합으로 즉시 판정하면 유효하지 않은 분기를 초기에 제거할 수 있습니다. 상태 복원이 정확하지 않으면 다음 분기에 오염이 전파되므로 제거 순서를 엄격히 지켜야 합니다.

평균 시간복잡도: 입력 구조 의존
최악 시간복잡도: 대략 지수(O(N!)에 가까운 탐색 분기 가능)
공간복잡도: 재귀 스택 O(N) + 상태 집합

백트래킹: 중복 원소 순열 생성

문제 의도: 정렬 + 방문배열 + 같은 레벨 중복 제거로 유일 순열만 생성합니다.
입력 예시: nums=[1,1,2]
출력 예시: [[1,1,2],[1,2,1],[2,1,1]]

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void dfsUnique(
    const vector<int>& nums,
    int depth,
    vector<bool>& used,
    vector<int>& path,
    vector<vector<int>>& out
) {
    if (depth == (int)nums.size()) {
        out.push_back(path);
        return;
    }
    for (int i = 0; i < (int)nums.size(); ++i) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        dfsUnique(nums, depth + 1, used, path, out);
        path.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> uniquePermutations(vector<int> nums) {
    sort(nums.begin(), nums.end());
    vector<bool> used(nums.size(), false);
    vector<int> path;
    vector<vector<int>> out;
    dfsUnique(nums, 0, used, path, out);
    return out;
}

int main() {
    auto ans = uniquePermutations({1, 1, 2});
    for (auto& row : ans) {
        cout << "[";
        for (int i = 0; i < (int)row.size(); ++i) cout << row[i] << (i + 1 == (int)row.size() ? "" : ", ");
        cout << "] ";
    }
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static List<List<Integer>> uniquePermutations(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> out = new ArrayList<>();

        class Solver {
            void dfs() {
                if (path.size() == nums.length) {
                    out.add(new ArrayList<>(path));
                    return;
                }
                for (int i = 0; i < nums.length; i++) {
                    if (used[i]) continue;
                    if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
                    used[i] = true;
                    path.add(nums[i]);
                    dfs();
                    path.remove(path.size() - 1);
                    used[i] = false;
                }
            }
        }

        new Solver().dfs();
        return out;
    }

    public static void main(String[] args) {
        System.out.println(uniquePermutations(new int[]{1, 1, 2}));
    }
}

main.py

def unique_permutations(nums):
    nums.sort()
    used = [False] * len(nums)
    path = []
    out = []

    def dfs():
        if len(path) == len(nums):
            out.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue  # 같은 레벨 중복 제거

            used[i] = True
            path.append(nums[i])
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return out

print(unique_permutations([1, 1, 2]))
# 출력: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

main.rs

fn unique_permutations(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
    nums.sort();
    let mut used = vec![false; nums.len()];
    let mut path = Vec::new();
    let mut out = Vec::new();

    fn dfs(nums: &[i32], used: &mut [bool], path: &mut Vec<i32>, out: &mut Vec<Vec<i32>>) {
        if path.len() == nums.len() {
            out.push(path.clone());
            return;
        }
        for i in 0..nums.len() {
            if used[i] {
                continue;
            }
            if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] {
                continue;
            }
            used[i] = true;
            path.push(nums[i]);
            dfs(nums, used, path, out);
            path.pop();
            used[i] = false;
        }
    }

    dfs(&nums, &mut used, &mut path, &mut out);
    out
}

fn main() {
    println!("{:?}", unique_permutations(vec![1, 1, 2]));
}

중복 제거 분기 선정 배경

중복 제거 조건을 넣지 않으면 동일 순열을 여러 번 생성해 시간과 메모리를 낭비합니다. 이 조건은 같은 깊이에서 같은 값의 첫 선택만 허용한다는 의미입니다. 문제 성격에 따라 중복 허용 여부를 우선 고정해야 합니다.

평균 시간복잡도: 입력 구조 의존
최악 시간복잡도: O(N! ) 근사
공간복잡도: 재귀 스택 O(N) + 결과 저장

백트래킹 가지치기 비용 균형점

백트래킹 설계의 균형점입니다.

강한 가지치기: 빠르지만 안전성 검증이 어려움
약한 가지치기: 안전하지만 성능 이점이 작음
전역 상태 사용: 구현 단순, 복원 버그 위험 증가
불변 구조 사용: 안전성 높음, 메모리/복사 비용 증가

목표가 해 하나인지 모든 해인지도 성능에 큰 영향을 줍니다.

가지치기 누락 반례와 복구 절차

대표 오류는 아래와 같습니다.

전제 없는 가지치기로 정답 분기 삭제
복원 누락으로 상태 오염
중복 제거 규칙 부재
조기 종료 플래그를 깊이별로 일관되게 처리하지 않음

반례로는 최소 입력, 중복 다수, 해 없음 케이스를 반드시 포함하세요.

백트래킹 성능 구간 정리

비용 상쇄 지점 판단 시에는 평균 성능뿐 아니라 최악 입력 분포, 메모리 제약, 구현 복잡도를 함께 비교해야 합니다.

문제	평균 시간	최악 시간	공간
부분집합 합	데이터 의존	`O(2^N)`	`O(N)`
N-Queen	데이터 의존	대략 지수	`O(N)` + 결과
중복 순열	데이터 의존	`O(N! )` 근사	`O(N)` + 결과

백트래킹은 최악 차수보다 실제 가지치기 효율이 체감 성능을 결정합니다.

가지치기 과적용 실패사례 체크 포인트

가지치기 조건은 문제 전제와 함께 주석으로 남겨야 합니다.
큰 입력에서는 재귀 깊이 제한을 우선 확인하세요.
탐색 트리 크기 추정치를 기록하면 최적화 우선순위를 잡기 쉽습니다.
결과 수가 큰 문제는 생성 즉시 소비(streaming) 전략을 검토해야 합니다.

백트래킹 품질 체크포인트

가지치기 조건이 정답 분기를 제거하지 않음을 확인했는가
상태(방문, 열/대각선, 현재합)를 명확히 분리했는가
중복 제거 규칙을 입력 정렬과 함께 적용했는가
빈 입력/해 없음/중복 다수 반례를 테스트했는가

백트래킹 가지치기 정리

백트래킹은 무식한 완전 탐색이 아니라 유효한 분기만 남기는 설계 기술입니다. 상태 복원과 안전한 가지치기를 함께 관리하면 지수형 문제도 충분히 다룰 수 있는 수준으로 줄일 수 있습니다.

백트래킹과 가지치기 전략 설계

목차