[알고리즘] 백트래킹(Backtracking)

백트래킹

 : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법으로 최적화 문제와 결정 문제를 푸는 방법이다!

 

DFS와 백트래킹

- DFS : 가능한 모든 경로를 탐색하기 때문에, 불필요할 것 같은 경로를 사전에 차단하는 등의 과정이 없어 경우의 수를 줄이지 못한다.

 

- 백트래킹 : 해를 찾아가는 도중 지금의 경로가 해가 될 것 같지 않으면 그 경로는 더이상 가지 않고 되돌아간다. 따라서 반복문의 횟수까지 줄일 수 있으므로 효율적이다.

이를 "가지치기" 라고 하는데, 불필요한 부분을 쳐내고 최대한 효율적으로 간다는 의미이다.

 

즉, 백트래킹은 모든 경우의 수 중 특정 조건을 만족하는 경우만 살펴본다.

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

 

백트래킹 관련 문제 포스팅 : https://gr616.tistory.com/348