백트래킹

저번 시간에 DFS, BFS 에서 다뤘는데 이들은 모든 노드를 참조한다는 그런 탐색 방법이다.

 

하지만 이미 조건에서 벗어난 경우에도 나머지 노드들을 탐색을 계속해서 진행해야할까?

그럴경우엔 괜히 자원 낭비가 될수가 있다.

 

이럴때 사용하는것이 백트래킹 기술이다.

• 백트래킹(Backtracking)즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됨
• 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미
• 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아감

---

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