백트래킹?
해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법이다.
모든 경우의 수를 전부 고려하는 알고리즘이며, 일종의 트리 탐색 알고리즘이다.
방식에 따라서 깊이우선탐색(DFS)과 너비우선탐색(BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다.
모든 경우의 수를 고려하는 문제라면 DFS가 일반적으로 편리하다.
그러나 DFS를 절대 쓰면 안되는 경우는 트리의 깊이가 무한대가 될 때이다.
미로찾기에서 루프(회로)가 발생하는 경우 DFS는 이 가지를 탈출할 수 없다.
분기점 없이 길이가 길면 스택 오버플로우가 발생할 수 있다.
따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다.
백트래킹은 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지않고 되돌아간다.
코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.
불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다라는 의미에서 가지치기라고 한다.
그래서 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. N!의 경우의 수를 가진 문제에서 최악의 경우 지수함수 시간을 필요로 하므로 처리가 불가능 할 수 있기 때문이다.
DFS(Depth First Search)
상태공간을 나타낸 트리에서 바닥에 도달할 때까지 한 쪽 방향으로만 내려가는 방식이다. 미로찾기로 예를 들면, 한 방향으로 들어갔다가 막다른 길에 다다르면 왔던 길을 돌아가서 다른 방향으로 간다. 목표지점이 나올 때까지 반복한다.
이 알고리즘은 재귀함수로 구현할 수 있으며, 스택을 써서 할 수도 있다.
BFS(Breadth First Search)
모든 분기점을 전부 검사하면서 상태공간을 탐색하며 진행하는 방식이다.
BFS는 큐를 써서 구현한다. 각 경우를 검사하면서 발생하는 새로운 경우를 큐에 집어넣고, 검사한 원소는 큐에서 뺀다. 공간 복잡도가 지수 스케일로 폭발하기 때문에 가지치기를 제대로 안하면 DFS보다 빨리 오버플로우에 다다를 수 있다.
백트래킹은 가지치기(Purning)을 통해 효율을 극대화하며 가능한 모든 방법을 탐색하는 알고리즘이다.
참고 링크
