백트래킹이란?

• 문제를 해결하기 위한 탐색 기법
• 문제를 해결할 수 있는 모든 경로를 탐색하면서 선택한 경로가 유효하지 않거나 조건에 만족하는 해를 찾지 못할 경우, 이전 단계로 되돌아가 다른 경로를 시도
• 재귀함수 형태로, DFS의 개념과 구현방식이 매우 유사함.
  • DFS: 모든 노트 탐색
  • 백트래킹: 조건을 만족하는 해를 찾기 위해 불필요한 경로는 조기 차단(가지치기)