백트래킹 알고리즘 (BackTracking)

백트래킹

주어진 문제의 가능한 경우의 수를 모두 탐색하면서 해를 찾는 알고리즘
해당 방법은 재귀함수를 통해 해결하며, 모든 가능한 해를 시도하되,
특정 조건에 맞지 않으면 그 경로를 포기하고 이전 단계로 돌아간다.
=> 되돌아 가서 다시 해를 찾는다. (백트래킹)

1. 문제를 작은 부분으로 나눈다.
2. 조건을 만족하는지 확인한다.
3. 재귀적으로 해결한다. == 가능성 탐색
4. 해를 찾으면 기록하고(가능성 o), 아니면 되돌아간다. (가능성 x == 백트래킹)

일반적 코드 형태

public static void 재귀함수(자료형 n);
 if(bool) { }
 else { for 반복문 }

모든 경우의 수에서 조건을 만족하는 경우를 탐색한다는 점에서
=> 완전 탐색 기법 BFS(너비 우선 탐색), DFS(깊이 우선 탐색)로 모두 구현 가능

DFS와 백트래킹 차이점

DFS: 모든 경로를 추적
백트래킹: 노드의 유망성을 따져 가지치기(pruning)를 통해 불필요한 경로는 탐색하지 않는다.