[Algorithm] 백트래킹(Back Tracking)

📍백트래킹이란 ?

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

즉, 해를 찾을 때 중간에 해가 아니어서 막힐 경우, 이전 단계로 되돌아가 해를 다시 찾는 기법

 

📍백트래킹의 쓰임

최적화 및 조합, 결정 문제를 풀 때 쓰인다.

주로 DFS(깊이 우선 탐색)와 묶여서 잘 쓰이는데, DFS는 가능한 모든 경로를 탐색한다.

따라서, n이 큰 경우 경우의 수를 줄여야 할 필요성이 있다.

→ 이 때 백트래킹을 사용하여 불필요하거나 불가능한 경로를 사전에 차단하는 것을 통해 경우의 수를 줄일 수 있다.

 

즉, 가지치기를 할 수 있다는 것 !

 

▶  DFS와 쓰일 때 흐름은 다음과 같다.

 

DFS로 모든 경우의 수를 탐색할 때,

1. 조건문을 걸어 불가능한 경우를 정의하고,
2. 해당 상황일 때 탐색을 중지
3. 이후 그 이전으로 돌아가 다른 경우를 탐색하도록 구현

따라서 이전으로 돌아가 다른 경우를 탐색하도록 구현해야 하므로 백트래킹은 재귀와 함께 쓰인다.

---

📍 대표 예시

백트래킹의 대표적 문제로 N과 M 시리즈가 있다.

문제 링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

▶ C++ 코드

#include <iostream>

using namespace std;

int n, m;
int arr[9];
bool check[9]; // check[i]에서 i 사용 여부 체크용 배열

void func(int k)
{
    if(k == m)
    {
        for(int i=0; i<m; i++)
            cout << arr[i] << ' ';
        cout << "\n";
        return;
    }

    for(int i=1; i<=n; i++)
    {
        if(!check[i])
        {
            arr[k] = i;
            check[k] = 1;
            func(k+1);
            check[k] = 0;
        }
    }
}

int main()
{
    cin >> n >> m;
    func(0);
    return 0;
}

 

func(k+1) 이후 k==m 인 조건을 만족했을 때, return을 통해 check[k]=0 이 실행되는 재귀 과정이 잘 이해가 되지 않아

n=4, m=3일 때를 예시로 들어 func(0)부터의 전체적인 흐름도를 그려보았다.

연두색 하이라이트 된 부분에서,

func(0)부터 시작하여 func(3)까지 진행한 경우 k(3) == m(3) 인 base condition을 만족하게 된다.

if(k == m)
    {
        for(int i=0; i<m; i++)
            cout << arr[i] << ' ';
        cout << "\n";
        return;
    }

그럼 위 코드를 통해 arr 배열 내에 있는 1 2 3 을 차례로 출력하게 되고, return이 실행된다.

for(int i=1; i<=n; i++)
    {
        if(!check[i])
        {
            arr[k] = i;
            check[k] = 1;
            func(k+1);
            check[k] = 0;
        }
    }

return 이후 func(k+1) 바로 아래 행인 check[k]=0 을 통해 check[3]의 값이 0으로 초기화된다.

그럼 이후 for문을 따라 3 다음인 4(arr[3]=4)인 경우, 즉 1 2 4의 경우에 대해 검사하게 된다.

이러한 과정을 통해 1~4 4개의 숫자 중 3개의 경우를 고를 수 있는 모든 조합을 검사 가능하게 되는 것이다.