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

제약을 확인하는 시점이 탐색량을 가른다

백트래킹은 후보 해를 한 단계씩 만들다가 제약을 어긴 경로를 즉시 포기하는 깊이 우선 탐색 절차다. 유효한 선택만 다음 단계로 확장하고, 더 진행할 수 없으면 변경한 상태를 되돌린다. 목표를 충족한 해는 기록한다.

이 방식은 상태 공간 트리를 전제로 한다. 루트에서 시작해 선택을 간선으로 이어가며, 노드는 부분 해 또는 부분 배치를 나타낸다. 리프는 완전한 해이거나 더 이상 진행할 수 없는 실패 상태가 된다. 제약이 강할수록 초기에 버려지는 분기가 많아져 가지치기 효과도 커진다.

⤢✕

탐색을 운영 가능한 범위에 묶으려면 종료 조건도 함께 설계해야 한다. 시간 또는 노드 한도를 넘으면 중단하고 베스트-소-파를 기록한다. 반복 심화나 우선순위 큐를 결합해 탐색 순서를 제어할 수 있으며, 재귀 깊이와 스택 사용량을 관찰해 복원 누락도 막아야 한다.

상태와 제약을 가볍게 유지하는 방법

상태는 비교와 해시에 적합하도록 불변 또는 경량 구조로 잡고, 후보 생성기는 현재 상태에서 가능한 다음 선택만 내놓는 편이 좋다. 변수와 값의 순서를 도메인 지식으로 정하면 초반 가지치기 폭이 달라진다.

제약 검사는 국소 제약과 전역 제약을 나눠 다룬다. 즉시 위반 여부를 확인할 수 있는 국소 제약은 먼저 검사해 탐색 폭을 줄이고, 비용이 큰 전역 제약은 캐시나 증분 갱신으로 처리한다. 목표 검사는 완전 해의 조건 충족 여부나 목적 함수의 개선 여부를 판단한다.

가지치기에는 불가능성 판정과 상한·하한을 이용한 bounding을 쓸 수 있다. 최소 남은 값, 최대 제약 변수 우선 같은 휴리스틱도 선택 순서를 바꾸는 데 쓰인다. Forward Checking과 간단한 Propagation을 결합하면 후보 도메인을 더 일찍 축소할 수 있다.

복원은 탐색의 일부다. 선택으로 바뀐 값만 스택에 남기고 되돌리는 구조를 O(1)~O(log n)으로 설계할 수 있다. 불변 구조나 차분 적용은 GC 압력과 메모리 사용량을 관리하는 방법이 된다.

제약이 촘촘한 문제에서의 활용

근무표 편성, 시험 배정, 장비 슬롯 할당에서는 사람·자원, 시간창, 호환성 제약을 입력으로 삼는다. 후보를 배정한 뒤 근무 규칙과 연속 근무 제한을 검사하고, 위반한 분기는 바로 잘라낸다. 완전 배정에 도달하면 결과를 기록한다. 휴일이나 선호 가중치는 목적 함수로 바꾸고 베스트-소-파 상한을 유지해 불필요한 분기를 제한할 수 있다.

컨테이너-노드 배치, 기능 토글 조합 검증, 패키지 의존성 해 해결도 같은 방식으로 다룰 수 있다. 노드 용량과 적합성 제약을 먼저 검사한 뒤, 가장 크거나 제약이 많은 항목부터 배치해 용량 초과 분기를 제거한다. 증분 자원 집계와 비지배 해 파레토 필터링은 탐색 폭을 줄이는 데 쓴다.

제약 기반 테스트 입력을 만들 때는 파라미터 값을 고르고, 형식·범위·상호 배타 조건을 위반하면 즉시 이전 선택으로 돌아간다. 조합 레벨의 커버리지 목표에 도달한 입력은 수집하며, t-wise 같은 커버리지 지표를 달성하면 탐색을 일찍 끝낼 수 있다.

작업 순서나 방문 제약이 많은 소규모 라우팅에서는 다음 방문 후보를 만들고 시간창·용량 제약을 확인한다. 하한 비용 추정으로 분기를 제한할 수 있다. 대규모 문제는 메타휴리스틱이나 CP-SAT로 이관하는 선택이 권장된다.

성능과 운영 제어의 균형

제약 강도와 순서화를 적용하면 완전 탐색과 비교해 탐색 노드를 10^2~10^6배 줄일 수 있으며, 이는 문제 구조에 따라 달라진다. N-Queens, Sudoku에서는 초기 가지치기만으로 평균 수 초에서 수 ms 수준으로 단축된 사례가 빈발한다.

최적화 문제에서는 베스트-소-파를 유지해 anytime 해를 제공하고, 제한 시간 안에서 가장 좋은 솔루션을 확보할 수 있다. 시간·노드 한도와 반복 심화를 도입하면 최악 실행 시간의 상한도 관리할 수 있다.

방법	성능(평균)	확장성	일관성(해 품질)	안정성(최악 시간)	운영 편의
완전 탐색	낮음	매우 낮음	보장	매우 나쁨	높음
백트래킹	중~높음	중간(제약 의존)	보장/anytime	제어 가능(한도 설정)	중간
분기 한정	중~높음	중간	보장(최적)	문제 의존	중간
동적 계획법	매우 높음(특정 구조)	높음(중복 하위문제)	보장	좋음	중간
SAT/CP Solver	매우 높음	높음	보장/증명	좋음	중~높음

분기 한정과 SAT/CP는 강한 경계함수나 전파를 포함하는 일반화된 프레임워크다.

N-Queens에서 보는 적용과 복원

환경은 Python 3.10+이며 표준 라이브러리만 사용한다. 아래 코드는 n×n 보드에 서로 공격하지 않는 n개의 퀸을 배치한다. 열과 두 대각선의 충돌을 검사해 제약 위배 분기를 즉시 가지치기한다.

from typing import List

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

    def dfs(r: int):
        if r == n:
            sol.append(board.copy())
            return
        # 휴리스틱: 중앙 열 우선(대칭 활용은 생략)
        for c in sorted(range(n), key=lambda x: abs(x - (n - 1) / 2)):
            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 sol

if __name__ == "__main__":
    solutions = solve_n_queens(8)
    print(f"solutions={len(solutions)}")
    # 첫 해 출력(행: 열 인덱스)
    if solutions:
        print(solutions[0])

탐색 시작 시 타임스탬프를 저장하고 각 호출에서 제한 초과를 검사하면 시간 제한을 둘 수 있다. 첫 행에서 탐색하는 열의 범위를 절반으로 제한한 뒤 해를 반사해 추가하는 방식으로 대칭도 배제할 수 있다.

탐색 전략을 문제 특성에 맞추기

제약이 가장 강한 변수를 먼저 고르고 값의 순서를 조정하면 실패를 앞당길 수 있다. 다만 휴리스틱 계산 비용은 늘어난다.

Forward Checking이나 간단한 아크 일관성(AC-3)으로 도메인을 줄이는 방법도 있다. 전파 비용과 구현 복잡도는 커진다. 목적 함수의 상한과 하한으로 분기를 제한하는 bounding은 휴리스틱 품질이 낮으면 이득이 제한될 수 있다.

시간·노드·메모리 한도에 anytime 전략을 결합하면 자원 사용을 제어할 수 있지만, 최적성 보장을 포기할 가능성이 있다. 백트래킹은 상태 설계와 제약 선검사, 순서화·전파·경계 전략을 함께 조정할 때 탐색 비용을 줄일 수 있다. 성능 병목이 확인되면 전파와 경계, 메타휴리스틱을 단계적으로 도입하거나 CP-SAT·분기 한정·솔버 활용을 검토할 수 있다.