Backtracking Algorithm

Method

백트래킹 알고리즘은 모든 솔루션을 탐색해볼 수 있는 방법이다. 탐색 과정은 Tree 자료 구조를 DFS(depth first order)로 탐색하는 것과 동일하다. Tree 자료 구조를 기준으로 Partial Candidates는 tree의 Node로 표현되고, 1 depth 마다 부모 노드의 partial candidates에서 자식 Node의 값이 추가된다.

 

수많은 솔루션에서 정답만 찾아야 한다면, 백트래킹은 다음과 같이 동작한다. DFS와 같이 root node에서 부터 tree를 재귀적으로 순회한다. 각 노드에서 알고리즘은 노드가 valid solution인지 체크한다. 만약 solution이 아니라면 스킵한다. 정답이라면 저장한다.

 

특정 Depth에서의 노드 값들의 배열을 저장해야 한다면, 정렬과 Loop를 동시에 사용하면 된다. 이는 Leet Code 17. Letter Combinations of a Phone Number를 참고하자. 2개 이상의 배열에 접근하고, 각 배열이 복수개의 요소를 가지고 있다면 백트레킹 알고리즘을 사용할 수 있다.  이 문제는 Recursion을 사용해서 다음과 같이 풀었다.

void GetLetter(int MaxDepth, int CurrentDepth, string& digits,  string& str, vector<string>& Retval)
{
    const int ASCIITrsfNum = 48;
    string strofDepth = arr[(int)digits[CurrentDepth - 1] - ASCIITrsfNum - 2];

    if (CurrentDepth == MaxDepth){
        for (int i = 0; i < strofDepth.size(); ++i){
            str.push_back(strofDepth[i]);

            Retval.push_back(str);

            str.pop_back();
        }
    }
    else{
        for (int j = 0; j < strofDepth.size(); ++j){
            str.push_back(strofDepth[j]);

            // Recursion
            GetLetter(MaxDepth, CurrentDepth + 1, digits, str, Retval);

            str.pop_back();
        }
    }
}

Pseudocode (from wikipedia 'backtracking')

Pseudocode는 wikipedia의 내용을 그대로 가져왔다.

1. root(P): return the partial candidate at the root of the search tree.
2. reject(P,c): return true only if the partial candidate c is not worth completing.
3. accept(P,c): return true if c is a solution of P, and false otherwise.
4. first(P,c): generate the first extension of candidate c.
5. next(P,s): generate the next alternative extension of a candidate, after the extension s.
6. output(P,c): use the solution c of P, as appropriate to the application.

procedure backtrack(P, c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(P, s)
        s ← next(P, s)

 

Examples

백트래킹 알고리즘은 '스도쿠'에 적용할 수 있다. (와우!)

Tree 구조 형태로 Planning되는 예제도 적용할 수 있을 것 같다.

Leet Code에서는 94. Combination Sum 문제를 풀어보면 된다.