= 퇴각 검색
- Backtracking(백트래킹)
: 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다.
: 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.
=> 특정한 조건을 만족하는 경우만 살펴보는 것
ex) 홀짝 만들기
A, B, C 세 사람이 가지고 있는 숫자를 차례대로 하나씩 줄 세운다.
단, 조건은 짝수나 홀수가 연속으로 2번 나오면 안된다.
이때 만들 수 있는 숫자를 모두 구하라.
(순서는 A-B-C)
- A=1 / B=4 / C=7 -> 가능
- A=1 / B=4 / C=8 -> 불가능
- A=1 / B=4 / C=9 -> 가능
- A=1 / B=5 -> 불가능 (바로 B의 다음 숫자로 넘어감)
- A=1 / B=6 / C=7 -> 가능
...
이런식으로 조건을 하나씩 대입해가면서 만약 조건에 맞지 않는다면 그 즉시 중단하고 다음 숫자로 넘어감
그리고 모든 경우를 탐색해 가능한 모든 숫자 조합을 찾아냄