백트래킹으로 제약 탐색 공간 줄이기

해가 될 수 없는 분기를 먼저 버리는 탐색

백트래킹은 상태공간 트리를 DFS로 따라가며 부분해를 만들어 가는 탐색 기법이다. 후보를 하나 고른 뒤 제약을 만족하는지 확인하고, 가능성이 없다고 판단되면 더 깊이 내려가지 않고 이전 상태로 되돌아간다. 후보 생성, 유망성 검사, 재귀 확장, 백트랙이 반복된다.

부분해 자체가 상태가 되고, 유망성 함수는 그 상태를 계속 확장할 가치가 있는지 판별한다. 불필요한 분기를 일찍 제거할수록 방문해야 할 탐색 노드가 줄어든다. 목표 상태에 도달하면 해를 기록하고, 모든 후보를 소진하면 실패를 반환한다. 최초 해만 찾을지, 최적 해를 갱신할지, 가능한 해를 모두 모을지는 목적에 따라 달라진다.

상태공간 트리에서 노드는 부분해이고 간선은 선택한 결정이다. 재귀 호출 스택은 현재 경로를 자연스럽게 표현한다. 되돌림 과정의 상태 복원 비용은 O(1) 또는 O(log n)을 목표로 설계할 수 있다.

⤢✕

입력 범위(n≥0), 메모리 상한, 타임아웃은 탐색 시작 전에 검토할 운영 제약이다. 결과 역시 최초 해, 최적 해, 모든 해 중 어떤 정책을 쓸지 정해야 한다.

유망성 함수와 후보 순서가 탐색 비용을 바꾼다

유망성 판별자는 제약 충족 여부, 경계(bound), 중복 제거를 이용해 후보를 줄인다. 비용 함수의 하한과 상한을 활용하면 Branch-and-Bound와 결합할 수도 있다.

후보의 순서도 중요하다. 정렬, 도메인 축소, 최소 남은 값(MRV), 가장 제약이 많은 변수 우선 전략은 실패할 분기를 더 이른 시점에 드러내는 데 쓰인다. 방문 집합, 비트마스크, 정규형(normal form)은 동일한 상태를 반복 탐색하지 않게 한다. 대칭성 제거와 메모이제이션도 같은 목적에 속한다.

실제 시스템에서는 최초 해 탐색, 최적 해 갱신, 모든 해 수집 중 하나를 고르고, 타임아웃·노드 한도·최대 해 개수 같은 운영 제약을 병행한다.

N-Queens에서 열과 대각선을 상태로 관리하기

N-Queens는 pos[row] = col 형태의 1차원 상태 표현을 사용할 수 있다. 같은 열 또는 대각선에 퀸이 놓이지 않도록 하며, 열과 대각선을 집합으로 관리하면 유망성 검사를 O(1)로 구성할 수 있다.

보드 차수 n을 검증한 뒤 행 단위로 DFS를 수행한다. 충돌이 확인되면 즉시 가지치기하고, n행까지 배치하면 해를 기록한다. 첫 행에서 절반의 열만 배치하는 방식처럼 대칭성을 제거하면 탐색을 절반으로 줄일 수 있다. 최악의 복잡도는 O(n!) 수준이지만, 가지치기가 강할수록 실제 탐색 노드 수는 크게 줄어드는 경향이 있다.

부분 집합과 순열에서 중복을 제어하는 방식

부분 집합 생성의 상태는 인덱스 i와 현재 부분집합 S다. 합, 용량, 개수 제한 같은 문제별 Bound를 둘 수 있다. 각 원소는 포함과 미포함의 2분기로 나뉘며, 입력을 정렬한 뒤 중복 값의 연속 구간을 건너뛰면 중복 결과를 제거할 수 있다. 합 제한이 있을 때 현재 합과 남은 원소의 최대합으로 목표 도달이 불가능하다고 판단되면 일찍 중단한다. 전체 탐색 공간은 2^n이다.

순열 생성에서는 현재 순열 P와 used[]를 상태로 둔다. 위치마다 후보를 순회하고, 유망성 검사를 통과한 후보를 사용 처리한 뒤 재귀 호출하고 다시 해제한다. 중복 원소는 정렬 후 동일 값의 첫 사용만 허용하며, 접두 제약처럼 부분해가 불가능한 조건이 나오면 가지치기한다. 전체 경우의 수는 n!이고, 중복 제거와 도메인 축소가 평균 시간을 줄인다.

Python 구현

전제조건: Python 3.10 이상, 표준 라이브러리만 사용.

from typing import List, Iterable

# N-Queens: 모든 해 또는 첫 해 탐색
def solve_n_queens(n: int, all_solutions: bool = True) -> List[List[int]]:
    if n < 1:
        return []
    cols = set()
    diag1 = set()  # r - c
    diag2 = set()  # r + c
    pos: List[int] = [-1] * n
    solutions: List[List[int]] = []

    def dfs(r: int) -> bool:
        if r == n:
            solutions.append(pos.copy())
            return not all_solutions  # False면 계속 탐색, True면 조기 종료
        # 간단한 대칭성 제거: 첫 행만 절반 탐색
        col_range = range(n // 2) if r == 0 and not all_solutions else range(n)
        for c in col_range:
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue
            pos[r] = c
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            stop = dfs(r + 1)
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
            pos[r] = -1
            if stop:
                return True
        # 대칭 보정: 첫 해만 찾는 경우 대칭 열도 검사
        if r == 0 and not all_solutions and n % 2 == 1:
            c = n // 2
            if c not in cols and (r - c) not in diag1 and (r + c) not in diag2:
                pos[r] = c
                cols.add(c); diag1.add(r - c); diag2.add(r + c)
                stop = dfs(r + 1)
                cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
                pos[r] = -1
                if stop:
                    return True
        return False

    dfs(0)
    # 대칭성 제거 사용 시 모든 해 수집 모드에서는 실제 총해 계산은 후처리 필요
    return solutions

# 부분 집합: 중복 허용 입력 처리, 선택적 합 제한
def subsets(nums: List[int], sum_limit: int | None = None) -> List[List[int]]:
    nums.sort()
    result: List[List[int]] = []
    path: List[int] = []

    def dfs(start: int, cur_sum: int):
        if sum_limit is None or cur_sum <= sum_limit:
            result.append(path.copy())
        else:
            return  # 가지치기
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue  # 중복 제거
            nxt = cur_sum + nums[i]
            # 남은 원소가 모두 양수이면서 sum_limit 존재 시 보수적 Pruning
            if sum_limit is not None and nxt > sum_limit:
                break
            path.append(nums[i])
            dfs(i + 1, nxt)
            path.pop()

    dfs(0, 0)
    return result

# 순열: 중복 원소 처리 포함
def permutations(nums: List[int]) -> List[List[int]]:
    nums.sort()
    used = [False] * len(nums)
    result: List[List[int]] = []
    path: List[int] = []

    def dfs():
        if len(path) == len(nums):
            result.append(path.copy())
            return
        prev = None
        for i, v in enumerate(nums):
            if used[i]:
                continue
            if prev is not None and prev == v:
                continue  # 같은 레벨에서의 중복 제거
            used[i] = True
            path.append(v)
            dfs()
            path.pop()
            used[i] = False
            prev = v

    dfs()
    return result

if __name__ == "__main__":
    # 예시 실행
    print("N-Queens(첫 해):", solve_n_queens(8, all_solutions=False)[:1])
    print("부분 집합(합≤5):", subsets([1, 2, 2, 3], sum_limit=5)[:5])
    print("순열(중복 처리):", permutations([1, 1, 2])[:6])

N-Queens에서 모든 해를 수집할 때는 대칭 최적화를 제거하는 편이 낫다. 대규모 n에서는 비트마스크 기반의 정수 연산 구현이 메모리와 속도 측면에서 우수하다.

완전탐색과 비교할 때 확인할 지점

방법	성능(시간)	확장성	일관성	안정성	운영 편의
완전탐색	지수적, 최대 분기 탐색	낮음	높음	높음	간단하나 실용성 낮음
백트래킹	지수적이나 평균 노드 수 감소	중간	높음	높음	구현 난이도 중간
백트래킹+휴리스틱/비트마스크	평균 10~10^3배 단축 가능	상대적 높음	높음	높음	파라미터·튜닝 필요

탐색 노드 수, 초당 노드 처리량, 메모리 피크 사용량은 정량지표로 측정할 수 있다.

제약 만족 탐색을 운영에 연결할 때

백트래킹은 교대 근무, 회의실 배정, 차량 라우팅 전처리 같은 스케줄링·자원 배치에 적용할 수 있다. 하드 제약을 먼저 충족하고 소프트 제약 위반을 최소화하는 탐색으로 구성한다.

하드웨어 BOM 호환성, 기능 플래그 조합 검증, 테스트 케이스 생성 같은 구성·설계 검증에도 사용할 수 있다. 제약 만족 검색(CSP) 프런트엔드에서는 소규모 인스턴스를 자체 백트래킹으로 처리하고, 대규모 인스턴스는 CP-SAT/ILP에 위임하는 하이브리드 파이프라인을 구성할 수 있다.

유망성 검사, 도메인 정렬, 대칭 제거를 적용하면 탐색 노드 수를 대폭 줄일 수 있다. 동일 입력에 대해 결정적 순서와 시드를 관리하면 결과의 일관성을 확보할 수 있고, 타임아웃·노드 한도·메모리 가드는 SLA 준수에 도움이 된다.

유망성 함수 설계를 먼저 두고 후보 순서에 도메인 지식을 반영한다. 비트마스크와 사전 계산 캐시로 O(1) 제약 검사를 구현할 수 있으며, 타임아웃·해 개수 상한·깊이 제한은 운영 리스크를 관리하는 장치가 된다.

휴리스틱 강도를 높이면 최적성 보장이 약해질 가능성이 있다. 캐싱과 비트마스크는 메모리 사용량을 늘릴 수 있고, 병렬 분할 탐색에는 스레드 안전성과 작업 균형화 비용이 따른다.