백트래킹 알고리즘 기록

백트래킹 알고리즘 : 재귀  + State Space Tree

 

Back tracking algorithms  : Possible solution 을 찾기 위해 반복하는 Brute force 알고리즘 

 

space tree 는 현재 모든 상태를 기록하는 것. 

 

n - queen 문제 (BOJ 9663)  예로 들면 Queen의 위치 state를 기록한 것.

 

이 때 2차원 배열 Q[i,j] = true(1) , false(0) 으로 기록할 이유는 없음.

2차원 map 에서 어떤 object의 유무에 대한 정보기록은

Q[i]= j 로 1차원 배열로 기록할 수 있음.   

 

1) 해당 Space tree에  (k- th 상태에 대한 기록을 하고) 

2) function(k+1) 로 Recursion funciton 호출 ( base condition 에 대해 유념)

- 해당 조건이 k+1 로 가면서 return 되거나 , 

3) 재귀 이후 Space tree에 대해 k-th state에 대한 조건을 erase 해줘야 함.