230320

1. 백트래킹

해를 찾는 도중 막힌 경우 되돌아가서 다시 해를 찾아가는 기법

• 지금 경로가 정답일 가능성이 없다면 경로를 가지 않고 되돌아감 (가지치기)

• 역추적 알고리즘이므로 탐색 이전 단계로 되돌아갈 수 있어야 함

• 일반적으로 재귀를 이용한 DFS로 구현