백트랙킹(Backtracking)

백트랙킹 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법.

• DFS와 백트랙킹의 차이?

- DFS : 

DFS는 가능한 모든 경로(후보)를 탐색합니다. 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 해동이 없으므로 경우의 수를 줄이지 못한다.

- 백트랙킹 : 

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아 가는 것 .

코딩에서 쓸데없는 반복문의 횟수를 줄일 수 있으므로 효율적이다. 

이러한 로직을 "가지치기"라고하며 불필요한 부분을 쳐내고 올바른 쪽으로 향한다는 의미이다.

만약 N!의 경우의 수를 가진 문제에서 최악의 경우 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다. 

---

• 즉 백트랙킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우한 살펴보는 것
• 답이 될 만하지 판단하고 그렇지 않으면 그 부분까지 탐색하지 않고 가지치기를 통해 걸러내는 것.
• 실질적으로는 DFS등으로 모든 경우의 수를 탐색하는 과정에서, 조건문으로 절대 답이 될 수 없는 상황을 정의하고, 그러한 상황일 경우 탐색을 중지한뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있다.

---

- 백트랙킹 기법의 유망성 판단

1. 어떤 노드의 유망성, 즉 해가 될 만하지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 간다.
2. 해가 될 가능성이 있으면 유망하다(Promising)고 판단한다.
3. 유망하지 않은 노드에 가지 않는 것 (조건문의 False)이라면 가지치기(Pruning)한다고 하는 것이다.

 

 

자료 출처:

chanhuiseok.github.io/posts/algo-23/

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제