[Algorithm] 백트래킹(Backtracking) 알고리즘 알아보기

 

 

백트래킹(Backtracking) 알고리즘이란 ❓

백트래킹(Backtracking)은 문제 해결을 위한 탐색 기법 중 하나로, 재귀적 탐색과 되돌리기(backtrack)를 활용하여 최적의 해를 찾는 방법입니다.

 

많은 최적화 문제, 조합 문제, 순열 문제  등에서 널리 사용되며, 가능한 해를 하나씩 시도하면서 해가 될 것 같지 않으면 더 이상 탐색하지 않고 되돌아갑니다.

 

여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 합니다.

 

백트래킹(Backtracking)의 기본 개념

백트래킹은 탐색 트리에서 깊이 우선 탐색(DFS) 방식으로 진행되며, 각 노드에서 가능한 모든 선택을 해본 후, 그 선택이 잘못된 경로일 경우에는 다시 되돌아가서 다른 선택을 시도하는 방식입니다. 

 

이러한 방식은 문제의 해결 공간이 매우 크고, 모든 가능한 해를 확인해야 할 때 매우 유용합니다.

 

결정 공간 (Decision Space)

 

백트래킹에서 중요한 개념 중 하나는 결정 공간(Decision Space)입니다. 

 

이는 문제 해결을 위해 선택할 수 있는 모든 가능한 경로 또는 선택지들의 집합을 말합니다. 이 결정 공간을 Decision Tree라고도 부르며, 트리 형태로 그릴 수 있습니다.

 

백트래킹 알고리즘은 이 결정 트리를 탐색하면서 유망한 경로만을 따라가고, 유망하지 않다고 판단되면 더 이상 진행하지 않고 되돌아가는 방식으로 최적의 해를 찾습니다.

 

결정 공간을 어떻게 구성하느냐에 따라 백트래킹 알고리즘의 성능과 효율성이 달라지므로, 이 공간을 효율적으로 탐색하는 전략이 중요합니다.

 

백트래킹(Backtracking)의 기본 흐름

1. 유망성 검사(Promising Check)

• 현재 경로가 해결책이 될 수 있는지 판단합니다.
• 경로가 유망하지 않으면 (해가 될 것 같지 않으면)그 경로는 더 이상 탐색하지 않습니다.

2. 재귀적 탐색 (Recursive Exploration)

• 현재 상태에서 선택할 수 있는 모든 옵션을 하나씩 시도합니다.
• 하나의 선택을 했을 때 그 선택이 유망하다면, 다음 단계로 재귀적으로 진행합니다.

3. 백트래킹 (Backtracking)

• 어떤 선택이 잘못된 경로로 이어졌다면, 그 경로를 되돌려서 다른 선택을 시도합니다.

 

백트래킹(Backtracking)의 문제

조합 문제

1, 2, 3, 4, 5에서 2개의 숫자를 뽑아 합이 6이 되는 조합을 찾는 문제

public class CombinationExample {
    static int[] nums = {1, 2, 3, 4, 5};
    static int target = 6;
    
    public static void main(String[] args) {
        findCombinations(0, 0, new StringBuilder());
    }

    public static void findCombinations(int start, int sum, StringBuilder path) {
        if (sum == target) {
            System.out.println(path.toString());
            return;
        }

        for (int i = start; i < nums.length; i++) {
            if (sum + nums[i] > target) continue; // 초과하면 더 이상 탐색하지 않음
            path.append(nums[i]).append(" ");
            findCombinations(i + 1, sum + nums[i], path); // 재귀 호출
            path.delete(path.length() - 2, path.length()); // 상태 복원
        }
    }
}

 

이 문제는 주어진 숫자들에서 합이 목표값인 6이 되는 조합을 찾아야 하는 문제로, 결정 공간에서 가능한 모든 선택을 시도하고, 그 중 잘못된 선택은 되돌려 가며 해결합니다.

백준 - N 과 M (1)

[백준, 15649번] N과 M(1) (백트래킹, Java)

 

백트래킹(Backtracking)의 장점과 단점

장점

• 효율적인 탐색
  • 백트래킹은 불필요한 탐색을 중지시키고, 해를 찾기 위한 공간을 효과적으로 줄여줍니다. 결정 공간을 잘 구성하면 탐색 시간을 크게 단축할 수 있습니다.
• 최적화 문제 해결 가능
  • 최적화 문제에서 유망한 경로만 탐색하므로 최적해를 빠르게 찾을 수 있습니다.
• 유연성
  • 문제의 규칙에 맞춰 깊이 우선 탐색과 상태 복원을 통해 다양한 문제를 해결할 수 있습니다.

단점

• 시간 복잡도
  • 최악의 경우 탐색 공간이 매우 커질 수 있어, 최악의 시간 복잡도는 지수적일 수 있습니다. 따라서 탐색 공간을 잘 축소할 수 있는 문제가 아니면 비효율적일 수 있습니다.
• 메모리 사용
  • 재귀적 호출을 사용하기 때문에 많은 양의 메모리를 사용할 수 있습니다.

 

백트래킹(Backtracking) Tip

1. 입력 크기를 먼저 확인하라

• 백트래킹은 탐색 공간이 크면 비효율적일 수 있으므로, N이 작거나 탐색 공간이 제한적인 경우에 적합합니다.
• N이 10~15 이하인 경우 백트래킹으로 해결 가능한 경우가 많습니다.

2. 가지치기(Pruning)를 최대한 활용하라

• 불필요한 탐색을 줄이는 가지치기는 백트래킹의 핵심입니다.
  • 유망하지 않은 경로는 즉시 탐색을 중단합니다.
  • 문제의 제약 조건을 빠르게 확인하고, 조건을 만족하지 않으면 탐색을 종료합니다.

3. 재귀 호출 전에 상태를 변경하고, 호출 후에는 복원하라

• 백트래킹은 상태를 변경하며 진행되기 때문에, 재귀 호출 후 상태 복원이 필수입니다.
  • 호출 전 visited 배열이나 path를 변경하고, 호출이 끝나면 이전 상태로 되돌립니다.
  • DFS를 사용하는 경우 visited[i]를 true로 설정하고, 재귀 호출 후 false로 복원합니다.