[Swift] BackTracking / 백트래킹 / 퇴각검색

BackTracking / 백트래킹 / 퇴각검색
여러 후보 해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘.
해를 찾는 도중 막히면 돌아가 다시 해를 찾아간다.

미로

1. 해를 찾아가는 과정은 '루트'에서 부터 시작. (루트 또한 하나의 부분해)

2. 현재 위치한 부분해에서 선택이 가능한 다음 부분해의 목록을 얻음.

3. 2 에서 얻은 목록의 부분해들을 하나씩 방문.

4. 방문한 부분해가 요구하는 조건을 만족시키면 그 자리에서 2, 3 과정을 수행하고, 그렇지 않으면 그 이전 부분해로 돌아 나와 다른 부분해를 시도.

5. 최종해를 얻을 때까지, 또는 모든 경우의 수를 확인해도 해가 없음을 확인했을 때 까지 2,3,4 과정을 차례대로 반복.