백트래킹 개념

출처 : chanhuiseok.github.io/posts/algo-23/

 

* 백트래킹 = 되추적 = Backtracking

 - 유망(promising)하면 탐색을 계속 진행하고, 유망하지 않으면 부모 노드로 다시 돌아가(Backtracking)는 기법

   (유망하다 = 해가 될 가능성이 있다)

 - 다시 말해, 탐색 중 유망성 검사를 통해 가지치기(pruning)를 하는 기법

 - DFS는 모든 노드를 탐색하지만, 백트래킹은 모든 노드를 탐색하지 않을 수 있다는 점에서, 성능 차이가 있음

 - 자식 노드로 내려갈 때는 방문 표시를 하고, 부모 노드로 올라갈 때는 방문 취소를 함으로써, 방문 여부를 마치 스택처럼 관리해야 하는데, 이는 주로 재귀 함수의 전후에 방문 여부를 변경해주는 식으로 구현한다. (아래와 같이)

void search(int x){
	if(x==N){
		cnt++;
		return;
	}

	for (int i = 0; i < N; ++i) {
		if(visited[x][i]!=-1) continue;
		visit(x,i,x,true); // 방문 표시
		search(x+1); // 재귀 함수
		visit(x,i,x,false); // 방문 취소
	}
}

 

 - 재귀 함수 전후로 vector.push_back()과 vector.pop_back()을 사용해서, 벡터의 요소를 스택처럼 관리하기도 한다. (아래와 같이)

void search(vector<int>& v) {
	// 해를 찾음
	if (v.size() == M) {
		for (int i = 0; i < v.size(); i++) {
			printf("%d ", v[i]);
		}
		printf("\n");
		return;
	}

	// 탐색
	for (int i = 0; i < list.size(); i++) {
		if (visit[i] == true) continue;
		visit[i] = true;
		v.push_back(list[i]); // 요소 삽입
		search(v); // 재귀 함수
		v.pop_back(); // 요소 삭제
		visit[i] = false;
	}
}