백 트래킹 (Back Tracking)

백 트래킹 (Back Tracking)

말 그대로 왔던 길을 다시 추적하는 알고리즘.

즉, 모든 경우를 전부 고려하는 알고리즘이다. 여기까지만 본다면

모든 경우를 하나하나 실험해보는 'Brute Force'가 떠오를 것이다. 

 

Brute Force와 다른점이 있다면, 가능성이 없는 답변은 탐색 대상에서 제거한다는 특징이 있다. 

Brute Force와는 차별화된 Back Tracking의 특징은

필요없는 값은 정답 후보군을 제거해주는 가지치기(Pruning 혹은 Branch and bound)이다.

이 가지치기를 통해 한번 갔던 루트 중, 재방문이 필요없는 루트는 탐색하지 않는다.

 

백 트레킹에는 크게 3가지 종류가 있다.

• 스택 혹은 재귀함수를 이용하는DFS(깊이우선탐색, Depth First Search),
• 큐를 이용하는 BFS(너비우선탐색, Breadth First Search)
• BFS/HS(최선우선탐색, Best First Search / Heuristic Search)

일반적으로 모든 경우의 수를 고려하는 경우에는 DFS를,

최단거리를 구하는 경우에는 BFS(너비우선탐색)을 주로 이용한다.

 

이미지 출처 : https://www.freelancinggig.com/blog/2019/02/06/what-is-the-difference-between-bfs-and-dfs-algorithms/

DFS와 BFS는 이름에서도 그 차이가 들어난다.

• BFS는 Breadth(폭, 너비)에서 볼 수 있듯이 수평방향으로 가장 가까이 인접해있는 길을 최우선으로 접근한다.
• DFS는 Depth(이름)에서 볼 수 있다싶이, 한 방향으로 깊숙히 들어가 더 이상 갈 수 없을때 가장 가까운 갈림길로 되돌아간다. 

 

보다 쉬운 설명은 하단의 블로그를 참고해보자.

1. BFS vs DFS 개념 설명 : blog.naver.com/zzaxowns/222063216935

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 최적의 해와 효율성

2. 쉽게 풀어본 DFS : https://stack07142.tistory.com/24

순열 (Permutation)