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

백트레킹이란?

• 모든 경우의 수를 탐색하는 알고리즘
• DFS,BFS를 이용할 수 있다.
• 효율을 위해 탐색하지 않아도 되는곳을 미리 막는 것을 가지치기(Pruning)라고 한다.
• 자바스크립트는 재귀 효율이 안좋기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다.
• 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다.

DFS와 백트래킹

DFS,BFS는 모든 경우의 수를 찾을 때도 사용한다. (완전 탐색)

백트래킹과 DFS는 분리가 애매한 개념이다. DFS는 재귀를 통해 탐색을 시작하여 가능한 모든 경로를 깊이 우선으로 탐색하는 것을 의미하고, 백트래킹 알고리즘의 경우 현재 탐색하는 길이 더 이상의 조건과 다르다고 판단되면 되돌아오는 것을 의미한다.

즉, 백트래킹과 DFS는 같은게 아니라 백트래킹의 방법 중 하나가 DFS 이다. (BFS 등 다양한 방법으로 백트래킹을 구현할 수 있다.)

백트래킹과 관련된 용어

• 유망함(Promising): 진행중인 경로가 해답을 찾을 가능성이 있을때
• 유망하지 않음(Nopromising): 진행중인 경로가 해답을 찾을 가능성이 없을때
• 가지치기(Pruning): 유망하지 않은 하위 트리를 잘라냄