[알고리즘] 백트래킹에 대해 공부해보자

DFS?

DFS는 끝이 나올 떄까지 한 방향으로 탐색하는 방식으로, 방향을 잘못 선정할 시 큰 손해를 볼 수 있다.

 

Back Tracking :  해당 방향에 답이 없다고 판단되면, 되돌아가서 다른 방향을 탐색하는 기법

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.

이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로만 가는 의미이다.

 

백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.

답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기를 하는 것이 백트래킹이다.

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