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

1. BackTracking 이란?

BackTracking은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한조건에 위배되는지(유망하지 않은지) 판단하고, 그러한 경우 해당 노드를 제외하고 다음단계로 나아가는 방식이다.

여기서 중요한점은 특정상태(노드)를 제외한다는 것이다.

 

BackTracking은 현재 노드에서 다음 노드로 나아갈 수 있는 모든 경우를 찾되, 그중 유망하지 않다면 현재에서 더이상 나아가지 않고 이전의 노드로 돌아가 다음노드를 검사한다. 

여기서 더이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기라고도 한다.

 

즉, 이 방법을 통해 우리는 모든 경우의 수를 체크하지 않고 필요한 것만 체크하여 전체 풀이 시간을 단축 할 수 있게 된다.

 

BackTracking을 사용해 해결할 수 있는 문제는 의사결정, 최적화, 열거하기 등의 경우가 있다. 

사실 BackTracking은 사용 가능한 경우가 많지만, 시간복잡도가 보통 Exponential(지수, 2n 꼴) 이며, 대부분 Dynamic Programming, 그리디 알고리즘 등으로 더 빠르게 해결 할 수 있다.