[Algorithms] Backtracking | 백트래킹

Backtracking

백트래킹

- 백트래킹 탐색에서는 탐색을 진행하다, 더 이상 진행할 수 없다면, 왔던 길을 되돌아가 다른 길을 찾는다.
- 즉, 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 통칭하는 개념이다.
- 백트래킹 알고리즘마다 DFS와 약간의 차이는 있겠지만, 기본적으로는 모두 DFS의 카테코리에 속한다.
- 백트래킹 알고리즘들이 모두 상태 공간 트리를 실제로 구성하여 수행하는 것은 아니지만,
  백트래킹의 진행 과정은 상태 공간 트리의 Root부터 Leaf까지 DFS 방식으로 탐색하는 것과 논리적으로 동일하다.
- 백트래킹에서는 상태 공간 트리를 탐색할 때, Parent에서 Child로 진행하며 최적해에 가까워져 가는데,
  Child로 진행하는중에 더 이상 진행할 가치가 없는(오답인) 노드를 맞딱드리면
  더 이상 해당 노드의 Child는 진행하지 않는다.
  (이를 두고, 가지치기와 유사하다하여 "Prunning"이라 부른다.)
  (이러한 점에서, 모든 노드를 조사하는 Brute Force와 Backtracking은 차이가 있다.)

* Depth-First Search (DFS) (깊이 우선 탐색) (URL)

[Algorithms] Depth-First Search (DFS) | 깊이 우선 탐색

---

Examples of Backtracking Algorithms (백트래킹 알고리즘을 사용한 예시)

* Mazing Problem (미로 찾기 문제) (URL)

* Graph Coloring Problem (그래프 색칠 문제) (URL)

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)