시작하기에 앞서 우선 되추적 즉 BackTracking 에 대해서 알아보자.
스택에 자식 노드를 넣기전에 유망한지 즉 해답이 될 가능성이 있는지! 확인한 뒤
유망하지 않다면 더 이상 깊에 들어가지 않고 부모 노드로 되돌아가면서 풀이 시간을 단축한다.
이러한 방식은 단순 깊이우선탐색을 했을 때보다 엄청나게 효율이 증가한다.

알고리즘에서의 백트래킹

모든 경우의 수를 전부 고려하는 알고리즘이며, '가능한 모든 방법을 탐색한다'는데 기본 아이디어가 있다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS), 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search)이 있다.

1. DFS (깊이우선탐색)

DFS는 상태공간을 나타낸 트리에서 바닥에 도달할 때까지 한 쪽 방향으로만 내려가는 방식이다.
미로찾기를 생각하면 쉬운데, 한 방향으로 들어갔다가 막다른 길에 다다르면(=트리의 바닥에 도착할 경우) 왔던 길을 돌아가서 다른 방향으로 간다. 이 과정을 목표 지점(=원하는 해)이 나올 때까지 반복한다.

• 장점 : 무한히 깊은 곳을 찾아야할 때 효과적임
• 단점 : 모든 곳을 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 가능성 있음

모든 경우의 수를 고려해야 하는 문제라면 DFS가 낫다.

2. BFS (너비우선탐색)

BFS는 모든 분기점을 다 검사하면서 진행하는 방식이다.

철수와 영희가 계단에서 가위바위보게임을 하고 있을 때, 철수가 원하는 지점에 갈 수 있는 최소 승리 횟수는 얼마인가? 같은 문제에서 효과를 발휘한다.
이 경우 DFS는 깊이가 무한인 경우에 빠져나오지 못하며, 중복 방지를 한다고 치더라도 올바를 해를 찾는데 시간이 많이 걸린다. BFS는 모든 분기를 다 검색하면서 상태공간을 탐색한다. 철수가 이겼을 때, 비겼을 때, 졌을 때를 검사하고, 그 경우마다 각각 또 다른 3가지 가능성을 전부 검사한다. 이러다가 어느 한 부분에서 원하는 해를 발견하면, 이것이 최단 거리가 된다.

BFS는 큐를 서서 구현한다. 각 경우를 검사하면서 발생하는 새로운 경우를 큐에 집어넣고, 검사한 원소는 큐에서 뺀다. BFS의 장점은 DFS가 못 건드리는 문제를 풀 수 있는 것이지만, 공간 복잡도가 지수 스케일로 폭발하기 때문에 가지치기를 제대로 안 하면 DFS보다 빨리 오버플로우에 다다를 수 있다.

3. 최선 우선 탐색

이 BFS에서 조금 더 발전한 방식이 Best First Search 방식이다.

큐 대신 우선순위 큐를 써서 구현하는데, 발생하는 새로운 경우를 순차적으로 검사하는 Breadth First Search와 달리, 현재 가장 최적인 경우를 우선적으로 검사하므로 상대적으로 효율적이다. 백트래킹은 모든 경우를 다 고려하기 때문에 최선 우선 탐색을 이용한다면 어지간해서는 해결할 수 있다.
다이나믹 프로그래밍으로 할 수 있는 것도 다 구현할 수 있으니 시간과 메모리만 해결하면 매우 유용하다.
위의 철수 영희 문제의 경우, 목적지점과 계속 반대로 가려는 가지는 굳이 탐색할 필요가 없으므로, 적절히 쳐내면 된다.