백트래킹

퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다.

백트래킹은 모든 조합을 시도해서 문제의 해를 찾는다. 이것이 장점이 될 수 있는 이유는 백트래킹의 구현 방법들이 많은 부분 조합들을 배제하기 때문이다. 결국 풀이 시간이 단축된다.

주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 깊이 우선 탐색을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 해결 방법이 더 없으면 더 이전의 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 못 찾을 경우, 이 문제의 해결책은 없는 것이다.

퇴각검색은 보통 재귀 함수로 구현된다. 재귀로 파생된 해결 방법은 하나 이상의 변수가 필요한데 , 이것은 현재 시점에서 적용할 수 있는 변수값들을 알고 있다. 퇴각검색은 깊이 우선 탐색과 대략 같으나 기억 공간은 덜 차지한다. 현재의 상태를 보관하고 바꾸는 동안만 차지한다. 탐색 속도를 높이기 위해, 재귀 호출을 하기 전에 시도할 값을 정하고 조건(전진 탐색의 경우)을 벗어난 값을 지우는 알고리즘을 적용할 수 있다. 아니면 그 값을 제외한 다른 값들을 탐색할 수도 있다.

요약 : 백트래킹은 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다. 여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning) 라고도 한다.

백트래킹의 주요 개념

배열 A에서 N개를 뽑는 예제(조합 문제)

vector<bool> check(N, false);
void recursion(int M, int count, int index)
{
    if(count==M)
    {
        //선택한 원소를 기반으로 결과를 계산하는 부분
        return;
    }

    for (int i = index; i < N; i++) //원소 선택
    {
        if (!check[i])
        {
            check[i] = true; //원소 선택
            recursion(M, count + 1, i + 1);
            check[i] = false; //원소 해제
        }
    }
}

만일 이 문제를 브루트 포스로 풀려 하였으면, 다중 for문으로 찾아야 하였으며, 중복되는 연산이 존재하여 시간 복잡도가 증가하였을 것이며, N개의 for문을 겹쳐야 하는데, N이 주어지지 않는다면, 구현도 불가능 했을 것.

위의 코드를 보면 백트래킹은 DFS와 유사한 것을 알 수 있다. 둘 다 스택 구조(함수 호출은 스택 구조)이다. 하지만 DFS의 경우 가능한 모든 경로를 탐색하기에 불필요한 경로까지 모두 탐색한다.

백트래킹으로 풀 수 있는 문제는 대략 다음과 같다.

• 원소 선택
• 순열
• 중복 순열
• 조합
• m개 선택문제
• N-Queen 문제
• 미로 찾기
• 스도쿠, 퍼즐
• 그래프 경로 탐색 (예: Hamiltonian path)

예제 문제 : 14888 연산자 끼워넣기

#include<bits/stdc++.h>
#define endl "\n"

using namespace std;

long long MINN=INT_MAX, MAXX=-INT_MAX;
int oper[4];
vector<long long> Q;

void rec(int index, long long curr);

int main()
{
    int N,M;
    cin>>N;
    
    for(int i=0; i<N; i++)
    {
        cin>>M;
        Q.push_back(M);
    }

    cin>>oper[0]>>oper[1]>>oper[2]>>oper[3];

    rec(0,Q[0]);

    cout<<MAXX<<endl;
    cout<<MINN<<endl;
}

void rec(int index, long long curr)
{
    if(index==Q.size()-1)
    {
        MINN=min(MINN,curr);
        MAXX=max(MAXX,curr);
        
        return;
    }

    for(int i=0; i<4; i++)
    {
        if(oper[i]>0)
        {
            oper[i]--;
            
            if(i==0)
                rec(index+1, curr+Q[index+1]);
            else if(i==1)
                rec(index+1, curr-Q[index+1]);
            else if(i==2)
                rec(index+1, curr*Q[index+1]);
            else if(i==3)
                curr<0?rec(index+1, -((-curr)/Q[index+1])):rec(index+1, curr/Q[index+1]);

            oper[i]++;
        }
    }
}

재귀함수를 통하여 모든 경우를 테스트 하는 함수이다. (조합) 주로 최대 입력 가능한 횟수와 (여기서는 Q.size()-1) 현재 사용한 갯수를 나타내는 index변수가 같을 때까지 반복하는 것으로 구함 후위 감소 연산자와 후위 증가 연산자 사이에 재귀함수를 사용하는데 그 전달인자의 index에 1더한 값을 재귀시켜 한 개의 자원(상태)을 소모한 것으로 생각하게 한다.

풀 문제 (인 당 5문제 이상 풀어올 것)

15649 : N과 M (1) 15650 : N과 M (2) 15651 : N과 M (3) 15652 : N과 M (4) 15654 : N과 M (5) 15655 : N과 M (6) 15656 : N과 M (7) 15657 : N과 M (8) 15663 : N과 M (9) 15664 : N과 M (10) 9663 : N-Queen 문제