알고리즘 14 백트래킹

백트래킹 

여러개의 후보해 중에서 특정 조건을 만족시키는 모든 해를 찾는 알고리즘 
ex_)  미로 탈출 알고리즘 
- 갈림길->무조건 왼쪽
- 막다른 곳이 나오면 되돌아 나와서 오른쪽 시도 

- 뿌리에서 해를 찾기 시작
- 현재 부분해에서 선택 가능한 다음 부분해 목록을 조회 
- 부분해를 하나씩 하나씩 방문
- 해가 될 수 있는 조건이면 위를 다시 실행 
- 아니면, 이전 부분해로 돌아나와서 다른 부분해를 실행 
- 위의 단계를 반복 

ex) 미로 탈출 찾기 
- 재귀호출 기반 백트래킹 

 

Algorithm/BackTracking at main · Sukmin-LanternK/Algorithm