[알고리즘] 백트래킹(Back Tracking)이란?

백트래킹(Back Tracking) 백트래킹은 깊이 우선 탐색(DFS)를 진행하며 탐색 중인 경로에 답이 없다고 판단되면 해당 노드를 제거하고, 탐색을 시작했던 부모 노드에서 바른 방향으로 다시 탐색합니다. 여기서 더 이상 탐색할 필요가 없는 노드를 제외하는 것을 가지치기(Pruning)이라 하고 해당 경로에 답이 있다고 판단되는 경우에는 유망하다(Promising)이라고 합니다.

즉, 백트래킹은 DFS탐색을 진행하며 유망한 조건을 만족하는 방향으로만 탐색하는 알고리즘입니다. 백트래킹 탐색 과정 ACG라는 단어를 찾는다고 가정했을 시 다음과 같은 순서로 탐색을 진행합니다.

DFS탐색을 진행하여 "A"노드에서 "B"노드를 방문합니다. A다음 찾는 단어는 C로 "B"노드가 아니기 때문에 가지치기를 하고 부모.....