백트래킹 알고리즘
미로 퍼즐을 푸는 문제를 풀 때 막따른 길이 나온다면 그길에서 다시 왔던 길로 되돌아가서 하나씩 길이 있는지 확인하면서 넘어가는 문제를 누구나 한번쯤 풀어본 적이 있을 것이다.
되추적 알고리즘은 지나왔던 길을 표시해놔서 옳지 않은 길을 체크해놓고 문제를 해결하면서 되돌아가서 잘못된 길로 들지 않게 한다.
되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 대표적인 문제 사례로는 n-queen문제가 있다.
되추적은 트리의 변형된 깊이 우선 탐색이다. 깊이 우선 탐색은 일반 그래프를 대상으로도 정의할 수 있지만 여기서 되추적은 트리 검색에 국한하기 떄문에 단순히 트리의 검색만 설명한다. preorder 트리 탐색은 트리의 깊이우선 탐색이다. 이는 root 노드를 먼저 방문한 후, 그 뿌리마디의 후손들을 모두 방문한다. 깊이 우선 탐색은 더 이상 탐색할 것이 없는 노드까지 방문한다. 재귀를 활용한다.
깊이 우선 탐색 pseudo code
void dfs(node v){
node u;
visit v;
for (each child u of v)
dfs(u);
}문제를 해결하기 위해서 이 알고리즘은 자식 마디를 방문하는 순서에 대해서는 언급하지 않았다. 그러나 앞에서 말했듯이 왼쪽에서 오른쪽으로 방문한다.
n = 4일 때 n-여왕말 문제를 되추적 기술로 설명하면,
같은 행에 절대 두 개의 말이 존재할 수 없다.
Grind