백트래킹

백트래킹 알고리즘

백트래킹(Backtracking)은 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙)해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제(CSP/Constraint Satisfaction Problems)에 특히 유용하다.

가능한 한 모든 방법을 탐색하면서 해결책을 찾는데, 목표까지 가능성이 유망하지 않은 경로를 차단하고 가능성 있는 루트를 검색하는 방법이다.

• Promising: 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다.
• Pruning (가지치기): 해당 트리에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지치기를 한다.

제약 충족 문제

백트래킹은 제약 충조 문제(CSP)를 풀이하는데 필수적인 알고리즘이다.

제약 충족 문제란 수많은 제약 조건(Constraints)을 충족하는 상태(States)를 찾아내는 수학문제를 일컫는다.

구현

• 트리 구조에서 재귀함수로 구현하며 만약 노드가 조건에 맞지 않는다면 다시 부모노드로 돌아가는 방식으로 해가 아닌 선택지를 골라낸다.

예제

백준 6603 로또
집합 S에서 6개의 수를 고르는데(조합) DFS를 사용하되 깊이 제한으로 6일때 결과 값을 도출한다.