[Algorithm] 백트래킹 (Backtracking)

[Algorithm] 백트래킹 (Backtracking)

 

백트래킹이란, 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘을 말한다. 답을 찾는 도중 답이 아니어서 막히면, 되돌아가서 다시 답을 찾아간다. 단, "조건을 만족" 할때 만이다. 즉, 모든 경우의 수를 모두 찾는 것보다 경우에 따라 훨씬 빠를 수 있다.

 

주로 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현한다.

 

---

백트래킹 기법의 유망성 판단

어떤 값이 해가 될만하다면 유망하다(promising)고 하며, 유망하지 않은 값에 가지 않는 것을 가지치지(pruning)한다고 한다. 유망하지 않다고 판단되면 그 값의 이전으로 돌아가(backtracking) 다음 값으로 넘어간다.

 

 

참고

https://jeongdowon.medium.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-backtracking-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-13492b18bfa1

https://blog.encrypted.gg/732?category=773649

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