가지치기 안전성 기준

백트래킹 가지치기 안전 기준

가지치기는 빨라지는 만큼 정답 후보를 버릴 위험도 있으므로, 버려도 되는 조건을 증명 가능한 형태로 둡니다.

상한 계산

남은 값으로도 목표 불가

부분합이나 점수의 최대 가능치를 계산해 목표에 닿지 못하는 분기만 중단합니다.

제약 선검사

놓기 전에 충돌을 확인

N-Queen처럼 행, 열, 대각선 조건을 추가 전에 검사하면 깊은 실패를 줄입니다.

중복 차단

같은 선택 순서를 한 번만

정렬 뒤 사용 여부와 이전 원소 조건을 함께 봐야 같은 순열이 반복되지 않습니다.

제출 전 남길 증거

부분집합 현재 합과 남은 합의 범위로 탐색 계속 여부를 결정합니다.
N-Queen 열과 두 대각선 집합을 갱신하며 충돌 검사를 O(1)에 가깝게 만듭니다.
순열 생성 같은 값은 같은 깊이에서 한 번만 시작하도록 방문 규칙을 둡니다.