[개념 정리] 백트래킹

백트래킹이 뭘까?

 

이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다.

 

백트래킹

백트래킹은 완전 탐색과 가지 치기를 결합한 방식입니다.

모든 가능한 해를 찾는 과정에서 불필요한 탐색을 줄여줍니다.

 

완전 탐색과 어떤 차이가 있을까요?

 

완전탐색은 모든 경우의 수를 전부 탐색하며 해를 찾는 방법입니다. 이 과정에서 불필요한 탐색이 발생할 수 있습니다.

백트래킹은 이러한 불필요한 탐색을 줄이고, 더 작은 시간복잡도를 가지고 찾고자하는 해를 찾을 수 있도록 해줍니다.

 

가지 치기란 무엇일까요?

 

백트래킹의 핵심 기법 중 하나입니다. 현재 탐색 중인 경로가 찾고자하는 해에 도달할 수 없다고 판단하는 경우, 가차없이 그 경로를 탐색하지 않고, 다시 되돌아가는 방법을 말합니다.

 

 

백트래킹은 어떻게 구현이 될까요?

 

백트래킹은 주로 재귀함수를 통해 구현됩니다. 탐색 가능한 경로를 시도하다가, 현재 경로에서 목표하는 해를 찾을 수 없다고 판단되면, return을 통해 이전 재귀 호출로 되돌아가는 방식으로 구현됩니다. 이러한 과정들을 반복하면서 최종적인 목표 해를 찾게 됩니다.

 

 

간단한 백트래킹을 사용한 문제 하나를 풀면서 알아보겠습니다.

 

백트래킹 활용

 

백준 N과 M

https://www.acmicpc.net/problem/15649

 

문제에서 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 구하라고 합니다.
이를 해결하기 위해, 수열의 길이가 M개가 되면 해당 수열을 출력하고, 더 이상의 탐색을 진행하지 않고 바로 되돌아가는 방식으로 백트래킹을 합니다.

 

 

백트래킹으로 구현한  코드는 다음과 같습니다.

private static  void dfs(int[] array, int depth, boolean[] visited, int m, int n) {

    if(depth == m) {
        for(int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
        return;
    }

    for(int i = 1; i <= n; i++) {
        if(!visited[i]) {
            array[depth] = i;
            visited[i] = true;
            dfs(array, depth + 1, visited, m, n);
            visited[i] = false;
        }
    }
}

 

 

백준에 제출한 결과는 아래와 같습니다.

 

 

이 코드에서 백트래킹을 위해 존재하는 구문은 어디일까요?

 

이 코드에서 백트래킹을 담당하는 구문은 바로 if문을 사용해 return을 해주는 부분입니다. 

if(depth == m) {
        for(int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
        return;
    }

 

탐색 중, 특정 조건을 만족하는 경우 더 이상의 탐색을 중단하고 즉시 return하여 이전 단계로 되돌아갑니다. 이렇게 조건을 만족하지 않는 경로를 조기에 차단함으로써, 불필요한 경로 탐색을 줄이는 것이 바로 백트래킹의 핵심입니다.

 

 

다른 백트래킹 문제를 하나 더 보겠습니다. 

 

 

백준 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

 

문제에서 구해야할 부분은 아래와 같습니다.

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

문제에 따르면, 아래와 같은 형태가 됩니다.
1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

문제의 어떤 부분에서 백트래킹을 사용할 수 있을까요?

 

이 문제에서 백트래킹을 사용하는 부분은, 주어진 수와 연산자를 모두 사용해 하나의 수식을 완성한 경우입니다.
이때, 더 이상 추가로 연산할 숫자가 남아있지 않으므로, 해당 수식의 결과를 계산하고, 즉시 return하여 이전 단계로 되돌아갑니다.

 

백트래킹으로 구현한 코드는 다음과 같습니다.

private static void dfs(int depth, int value) {
    if(depth == N - 1) {
        maxValue = Math.max(maxValue, value);
        minValue = Math.min(minValue, value);
        return;
    }

    if(cnt[0] > 0) {
        cnt[0] -= 1;
        dfs(depth + 1, value + A[depth + 1]);
        cnt[0] += 1;
    }

    if(cnt[1] > 0) {
        cnt[1] -= 1;
        dfs(depth + 1, value - A[depth + 1]);
        cnt[1] += 1;
    }

    if(cnt[2] > 0) {
        cnt[2] -= 1;
        dfs(depth + 1, value * A[depth + 1]);
        cnt[2] += 1;
    }

    if(cnt[3] > 0) {
        cnt[3] -= 1;
        dfs(depth + 1, value / A[depth + 1]);
        cnt[3] += 1;
    }
}

 

백준에 제출한 결과는 다음과 같습니다.

 

 

코드에서 보면 조건문으로 사용한 부분이 백트래킹을 적용한 부분입니다.

 if(depth == N - 1) {
        maxValue = Math.max(maxValue, value);
        minValue = Math.min(minValue, value);
        return;
    }

 

마지막 숫자인 경우에 최댓값과 최솟값을 갱신시켜 줍니다.

 

이번에 살펴본 두 문제 모두, 특정 조건을 만족하는 시점에 탐색을 중단하고(return), 다시 이전 단계로 되돌아가는 흐름을 통해 백트래킹을 적용했습니다.

 

 

정리

• 백트래킹은 완전 탐색 과정에서 조건을 만족하지 않는 경로를 미리 차단해 불필요한 탐색을 줄이는 기법입니다.
• 백트래킹은 탐색 대상이 되는 경우의 수가 많을 때, 효율적으로 해를 찾기 위한 핵심적인 기법으로 자주 사용됩니다.