백트래킹

Backtracking

알고리즘에서의 백트래킹은 모든 경우의 수를 전부 고려하는 알고리즘이다. 모든 경우의 수를 고려한다는 의미는 해를 찾는 도중에 해가 아니여서 막히게 되면, 되돌아가서 다시 해를 찾는 기법이다.

트리로 나타낼 수 있을 때 가장 적합한 방식이다. 그래서 트리 탐색 알고리즘이라고도 불리운다 그 종류는 크게 방식에 따라서

• 깊이우선탐색(Depth First Search, DFS)

• 너비우선탐색(Breadth First Search, BFS)

• 최선 우선 탐색(Best First Search/Heuristic Search)가 있다.

DFS

DFS는 상태 공간을 나타낸 트리에서 바닥에 도달할 때 까지 한 방향으로만 내려가는 방식이다. 즉, 막 다른 길에 다다르면 왔던 길로 돌아가서 다른 방향으로 진행하는 방식으로 알 수 있다. 구현 방식은 재귀함수와 스택이 있다.

dfs와 백트래킹은 차이점이 있다. 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우에만 확인하는 것이기 때문에

구현자체는 dfs나 위에 언급했던 bfs등을 활용해서 구현을 하고 원하는 조건문은 걸어서 답이 될 수 없는 경우를 확인해서 이런 경우에는 탐색을 중지하고 다시 돌아가서 다른 경우를 탐색하게 구현

BFS

BFS는 모든 분기점을 다 검사하면서 진행하는 방식이다. 이것의 단점은 만약 깊이가 무한인 경우에는 빠져나오지 못한다는 단점이 있다. 구현방식은 큐를 사용해서 진행한다. 각 경우를 검사하면서 발생하는 경우를 큐에 집어 넣고 검사한 원소는 큐에서 빼낸다.