nqueens

[백트래킹] 퇴각검색

BackTracking 백트래킹 = 퇴각검색 백트래킹은 한정 조건을 가진 문제를 풀려는 전략이다. 1950년대 미국 수학자 D.H.레머가 만들었다. 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각가의 변수들을 값이 있어야 한다. 퇴각 검색은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 장점이 될 수 있는 이유는 퇴각검색 구현 방법들이 많은 부분 조합들을 배제하기때문이다. 결국 풀이 시간이 단축된다. 주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 DFS를 사용한다. 탐색 중 오답을 만나면 이전 분기점으로 돌아..