1. 백트래킹 (Backtracking) 정의

• 임의의 집합에서, 주어진 기준(criterion)대로 원소의 순서를 선택하는 문제를 해결하는 알고리즘 설계 방법.
• 대표적 사례: n-Queens 문제, 부분집합의 합 문제(sum of subsets problem).
• 해답 후보 공간을 트리 구조(상태공간트리)로 모델링하고, 가지치기(pruning)를 통해 불필요한 경로를 제거.

2. 상태공간트리와 깊이우선검색(DFS)

• 상태공간트리(state space tree):

  모든 가능한 상태(해답 후보)를 트리로 표현.

  뿌리에서 잎 노드까지의 경로가 해답 후보를 나타냄.

• DFS:

  뿌리 노드에서 시작하여 가능한 한 깊게 내려간 뒤, 더 이상 진행할 수 없으면 이전 노드로 돌아가 탐색을 계속.

3. 백트래킹의 핵심 논리

• 유망성(promising):

  현재 노드가 해답의 일부가 될 가능성이 있으면 유망(promising), 그렇지 않으면 비유망(non-promising).

• 가지치기(pruning):

  비유망한 노드에서 즉시 탐색을 중단하고 부모로 돌아감.

  해답 가능성이 없는 부분공간을 검색하지 않음.

4. n-Queens 문제

4.1 문제정의

• n × n 체스판에 n개의 여왕말(Queen)을 서로 잡아먹히지 않도록 배치.

• 한 행에 하나씩 Queen을 두면서,

  같은 열/대각선에 있는지 검사(유망성 판단).

4.2 백트래킹 알고리즘(알고리즘 5.1)

• 각 깊이(depth) i에서 i번째 행에 Queen을 둘 column을 선택.
• col[i] = i번째 행에 Queen이 위치한 column 값.