01. Backtracking
- 브루트포스를 개선한 방식으로, 가능한 모든 옵션에 대해 체계적으로 찾아 나감(경로 따라 가다가 필요 없어지면 더이상 안 가고 버린 다음 다른 경로 찾아감)
-Search Space Pruning (가지치기)
- 탐색 공간에서 불필요한 경로를 제거함으로써 탐색을 효율적으로 줄이고, 더 빠르게 해를 찾을 수 있는 방법임
- 탐색하다가 필요 없어 보이면 더 이상 진행하지 않고 해당 분기 종료 → 재귀 호출에서 백트래킹으로 돌아옴
02. problem of Backtracking
1) Eight Queens Problem
- 체스판 위에 8개의 퀸을 배치, 서로 공격하지 않게 하는 문제
- 각 행에 퀸을 하나씩 배치하며서 유효하지 않은 경우 가지치기 수행함
2) Subset Sum(부분집합 합 문제)
- 주어진 숫자들의 부분집합 중 특정 합을 가지는 경우를 찾는 문제(배열안에서 어떤거를 고르든지 해서 합이 15가 되는 부분집합이 있는지 등)
- 현재 숫자를 포함하거나/ 포함하지 않는 두 가지 경우로 분기함
3) Hamiltonian Cycle (해밀턴 순환)
- 모든 정점을 한 번씩만 방문하고 시작점으로 되돌아오는 경로를 찾는 문제
- NP-Complete 문제로, 아직 효율적인 알고리즘이 없어서 백트래킹 이용함
- 과정
- 시작 정점을 경로 배열에 추가 → 현재 경로에서 방문하지 않은 인접 정점 추가 → 순환 조건 불만족시 백트래킹으로 이전 단계로 복귀함
-Pruning 과정(그래프 → 트리)
- 그래프의 정점들을 순서대로 방문하며 경로 확장 → 유효하지 않은 경로는 트리에서 가지치기 당하여 제외됨 → 최종적으로 가능한 경로만 남아 트리 형태로 시각화 할 수 있음
현재 위 상태: 시작점으로 되돌아가지 못하는 중 → 백트래킹 하자
1에서 다시 가보지만 그래도 못찾음 → 다시 백트래킹 하자
3까지 백트래킹 한 후 에야 찾음
