Backtracking

백트래킹

• 여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘
• 백트래킹이 다루는 문제들은 해가 하나 이상 존재합니다. 해가 둘일 수도, 셋일 수도, 수백, 수천 개일 수도 있습니다.
• 후보해가 많은 문제에서 해가 될 조건을 만족시키는 '진짜 해'를 효율적으로 찾는 것이 백트랙킹의 목적인것입니다.
• 트리에서 깊이 우선 처럼 탐색을 해나가면서 중간에 조건을 만족하지 않으면 다시 부모 노드로 돌아가 다른 길을 찾아 가는 것입니다.