[Algorithm] 백트래킹 BackTracking

🤖 Algorithm

---

🟦 Back Tracking

해결책을 찾아가는 과정에서 가능한 모든 옵션을 고려하고, 해결책이 될 가능성이 없다고 판단되면 되돌아가서 다른 옵션을 찾아보는 알고리즘 기법

✅ 모든 경우의 수를 확인해야하나 for문으로는 확인이 불가한 경우(루프의 횟수가 가변적)
➡️ loop의 깊이를 나타내는 변수를 사용하며 같은 깊이가 하나의 for문을 이룸
   (본인은 깊이를 나타내는 변수를 level이라 하여 사용함
    ex) 1 2 3 4 중에서 2개의 숫자를 고르는 경우
    -> 숫자 고른 것 0개 - level 0
    -> 숫자 고른 것 1개 - level 1
    -> 숫자 고른 것 2개 - level 2 -> loop 종료 조건 )

보통 재귀적으로 구현

현재 상태에서 가능한 모든 선택지를 시도
➡️ 각 선택지에 대해 다음 단계로 진행
➡️ 더 이상 나아갈 수 없는 상황이 되면 이전 단계로 돌아가서 다른 선택지를 시도

( 시간복잡도 제한을 고려했을 때, 중복 허용 -> N의 최댓값은 8, 중복 비허용 -> 10 )

🟦 예시 - BOJ 백준 15649번 N과 M (1)

출력할 값을 담는 nums 벡터, 입력 여부를 나타내는 flag 벡터, 몇 번 index까지 값을 채웠는지를 나타내는 level 변수를 선언하여 문제를 풀었다.

#include <iostream>
#include <vector>

using namespace std;

void BT(vector<int> &nums,vector<int> &flag, int N, int M, int level)
{

    if(level==M) 
    {
        for(int i=0;i<M;i++)
        {
            cout<<nums[i]<<" ";
        }
        cout<<'\n';
        return;
    }

    for(int i=0;i<N;i++)
    {
        if(flag[i]==0)
        {
            nums[level]=i+1;
            flag[i]=1;

            BT(nums,flag,N,M,level+1);
            flag[i]=0;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin>> N >> M;
    int level=0;

    vector<int> nums(M);
    vector<int> flag(N,0);

    BT(nums,flag,N,M,level);

    return 0;
}

예를 들어 N=4, M=2일 경우

BT(nums,flag,4,2,0)를 호출하면
for문에서 i=0 일 때
nums = [1, 0], flag = [1, 0, 0, 0]인 상태로 BT(nums,flag,4,2,1)을 호출한다.

BT(nums,flag,4,2,1)를 호출하면
i=0 일 때 동작 X,

i=1일 때 nums = [1, 2], flag = [1, 1, 0, 0]인 상태로
BT(nums,flag,4,2,2)를 호출하며 조건문에 따라 값들을 출력하고 종료한다.
BT(nums,flag,4,2,2)가 종료되면 flag[1] = 0 이 실행되므로 flag는 [1, 0, 0, 0]이 된다.

i=2일 때 nums = [1, 3], flag = [1, 0, 1, 0]인 상태로
BT(nums,flag,4,2,2)를 호출하며 조건문에 따라 값들을 출력하고 종료한다.
BT(nums,flag,4,2,2)가 종료되면 flag[2] = 0 이 실행되므로 flag는 [1, 0, 0, 0]이 된다.

마찬가지로 i=3일 때의 동작을 마무리하면

BT(nums,flag,4,2,0)의 i=1 일 때로 돌아가 동작한다.