개요백트래킹(Backtracking)은 가능한 모든 경우의 수를 탐색하되, 불가능하거나 의미 없는 경로는 조기에 차단(pruning)하는 완전 탐색 기법이다. DFS(깊이 우선 탐색)를 기반으로 하며, 부분 해(partial solution)를 점진적으로 구성해가다가 해답이 아니라고 판단되면 직전 상태로 되돌아가 다른 경로를 탐색한다. 퍼즐, 조합, 순열, 경로 탐색 등 다양한 문제에 사용된다.1. 개념 및 정의완전 탐색(Brute Force): 가능한 모든 경우를 시도백트래킹: 모든 경우를 시도하되, 유망하지 않은 경로는 가지치기(prune)재귀 호출 + 조건 기반 되돌아가기 형태로 구현됨2. 동작 구조 단계 설명 1현재 노드(상태)가 해답인지 확인2해답이면 출력 또는 저장3아니라면 다음 가능한 선택..
