[c++/알고리즘] 백트래킹 정의, 예시

백트래킹이란? - ( DFS + 조건문 )

​

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

모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 것이다.

​

일반적으로 불필요한 경로를 조기에 차단할 수 있기 때문에 경우의 수가 줄어들 수 있지만, 최악의 경우에는 여전히 지수함수 시간을 필요로 하기 때문에 처리가 불가능할 수 있다.

즉, 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

​

주로 문제 풀이에서는 DFS(깊이 우선 탐색) 등으로 모든 경우의 수를 탐색하는 과정에서 조건문을 걸어 답이 절대로 될 수 없는 상황을 정의하고 그런 상황일 경우 탐색을 중단한 뒤 그 이전으로 돌아가서 다른 경우를 탐색하게끔 한다.

 

백트래킹 과정

예시​

https://www.acmicpc.net/problem/15649

 

백트래킹의 가장 기본이 되는 문제인 것 같다. ( 이 문제가 가장 쉬운 듯 )