백트래킹 개념정리

백트래킹

결론적으로 간단히 이야기하자면 트리 형태로 검색을 해나가며 만약 제약 조건을 통과하지 못한경우 그상태에서 탐색을 종료하고 부모 노드로 돌아가서 다시 다른 자식을 검사하는것이다

-> 크리티컬 맞으면 다검사하겠지만 당연히 종료하고 돌아오는게 있을테니  완전 탐색보다 빠름 

 

Backtracking = Back (뒤) + Tracking (추적)

되추적, 퇴각 검색이라 불림

모든 경우의 수를 탐색하되, 문제가 요구하는 어떠한 제약 조건을 만족하지 않는 경우는 더이상 탐색하지 않고 종료하는 것

 

결론적으로 현재것을 까보는데 유망성(조건검사)를 검사후, 조건을 만족하지 못하면 부모노드로 돌아가 다른 자식노드를 검사하는것이다.

 

 

 

시간복잡도

 

-> 일반적으로 상태 공간 트리의 노드수에 비례한다.

그냥 트리가 쭉있다면  O(N!) = 사실상 완전 탐색 이지만

백트래킹은 중간에 검사후 버리는 가지들이 있기때문에 사실상은 더 빠르다.

 

 

푸는방법

주로 재귀를 이용해서 푼다

def backtracking(current node) {
	if  현재 해답에 도달했다면 {
		print(current 상태)
		return
	}	
	if(유망성검사 함수(current node)){
		for(자식노드 child) {
			backtracking(child) //재귀
		}
	}
	else {
		return   //유망하지 않으면 바로 종료하고 돌아감
	}
}

 

이걸 적절하게 변형해서 사용하면 풀릴거다.

 

 

문제유형: 완전 탐색으로 풀 수 있는 입력 제한이 작은 문제 + 가능한 경우의 수들이 모두 어떤 제약 조건을 통과할 때

이게 무슨소리인가 한참 생각했는데 가능한 경우의 수들이 모두 어떤 제약조건을 통과할때가 답으로 나올께 다 내가 걸어놓은 조건을 통과하는 경우를 말하는거같다.

대표적인 문제들 → 스도쿠, N-Queens(풀어볼 예정!), 0-1 knapsack problem 등

 

 

https://www.acmicpc.net/problem/9663

9663번: N-Queen

대표격 문제!!

---

출처 : sopt 동아리 스터디 솝탁의 개설자분들 알고리즘 킹들