백트래킹 (Back Tracking)

I. 모든 경우의 수 도출, 백트래킹

모든 경우의 수를 도출하기 위해 DFS와 Pruning 기법 기반 특정 조건 만족하는 모든 해 탐색 기법

II. 백트래킹 절차도 및 세부 절차

가. 백트래킹 절차도

• DFS 기반 유망성 부재 시 Pruning 수행하여 시간 단축

나. 백트래킹 세부 절차

절차	핵심 개념	설명
깊이 우선 탐색 수행	– 상태 공간 트리	– 상태 공간 트리 기반 Pre Order 방식 DFS 수행
Promising 검토	– 유망성 검토	– 해 존재 가능 시 서브 트리 – 해 부재 예상 시 백트래킹
서브 트리 이동	– 재귀 호출	– 방문 노드의 하위 노드로 이동 – DFS 기반 해 탐색
백트래킹 수행	– Pruning	– 방문 노드에 Pruning 수행 – 상위 노드로 백트래킹

다. 백트래킹 구성요소

구분	구성요소	설명
노드	Non-Promising	– 해답이 나올 가능성이 없는 마디
	Promising	– 해가 나올 만한 유망한 마디
해	모든 해	– 해당 문제 해결 위한 모든 해
	후보 해	– 해가 될 수 있는 집합
기법	DFS	– 깊이 우선 탐색 모든 기법
	Back-Tracking	– 가능성 없는 마디 제거(Pruning)

III. 백트래킹 예제기반 원리 설명