6. 알고리즘 백트래킹

백트래킹(Backtracking)은 문제의 해를 찾는 도중에 해의 조건을 만족하지 않는 경우, 해당 부분을 더 이상 탐색하지 않고 이전 단계로 돌아가는 기법입니다. 즉, 해를 찾기 위해 가능한 모든 경우를 탐색하되, 조건을 만족하지 않으면 되돌아가서 다른 경우를 탐색하는 방법입니다. 백트래킹은 주로 조합 문제, 순열 문제, 그래프 문제 등에 사용됩니다.

백트래킹의 동작 원리

1. 해를 찾기 위한 선택

주어진 문제에 따라 선택을 하여 해를 찾아나갑니다. 이때 선택은 여러 개의 후보 중 하나를 선택하는 것입니다.

2. 선택의 유효성 검사

선택한 후보가 주어진 조건을 만족하는지 확인합니다. 선택한 후보가 조건을 만족하지 않는다면 해당 선택을 취소하고 다른 후보를 선택합니다.

3. 해의 조건 만족 여부 확인

선택한 후보가 해의 조건을 만족하는지 확인합니다. 해의 조건을 만족한다면 문제의 해를 찾았으므로 결과를 반환하거나 출력합니다.

4. 다음 선택으로 이동

선택한 후보가 조건을 만족하고 해의 조건을 만족하지 않는다면, 다음 선택으로 이동하여 다시 선택을 진행합니다. 이때 백트래킹을 통해 이전 단계로 돌아갑니다.

백트래킹은 재귀적인 구조로 구현되는 경우가 많습니다. 일반적으로 백트래킹 알고리즘은 깊이 우선 탐색(Depth-First Search, DFS)과 함께 사용됩니다. 백트래킹 알고리즘을 구현할 때는 주로 재귀 함수를 사용하여 선택, 조건 검사, 해의 조건 확인, 다음 선택으로 이동하는 과정을 반복적으로 수행합니다.

백트래킹은 가능한 모든 경우를 탐색하지만, 가지치기(Pruning) 기법을 사용하여 필요한 경우만 탐색하도록 최적화할 수 있습니다. 이를 통해 백트래킹 알고리즘의 효율성을 향상시킬 수 있습니다.

백트래킹은 조합 최적화, 순열 생성, 그래프 탐색, 스도쿠, N-Queen 문제 등 다양한 문제에서 활용됩니다.

예시

예시로 조합(combination) 문제를 풀어보겠습니다.

import java.util.ArrayList;
import java.util.List;

public class Combination {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int k = 2;
        List<List<Integer>> combinations = generateCombinations(nums, k);
        System.out.println(combinations);
    }

    public static List<List<Integer>> generateCombinations(int[] nums, int k) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        backtrack(nums, k, 0, current, combinations);
        return combinations;
    }

    public static void backtrack(int[] nums, int k, int start, List<Integer> current, List<List<Integer>> combinations) {
        // Base case: 조합의 크기가 k가 되면 결과에 추가
        if (current.size() == k) {
            combinations.add(new ArrayList<>(current));
            return;
        }

        // 가능한 선택지 탐색
        for (int i = start; i < nums.length; i++) {
            // 선택한 요소를 현재 조합에 추가
            current.add(nums[i]);
            // 재귀적으로 다음 요소 선택
            backtrack(nums, k, i + 1, current, combinations);
            // 백트래킹: 선택한 요소를 현재 조합에서 제거
            current.remove(current.size() - 1);
        }
    }
}

위의 코드는 주어진 배열 nums에서 크기가 k인 조합을 생성하는 예시입니다. generateCombinations 메서드는 백트래킹을 활용하여 조합을 생성하고, backtrack 메서드는 실제로 백트래킹을 수행합니다.

• backtrack 메서드:

  • Base case: 현재 조합의 크기가 k와 같으면 결과에 추가하고 종료합니다.

  • 재귀적으로 가능한 선택지를 탐색합니다.

  • 선택한 요소를 현재 조합에 추가한 뒤, 다음 요소를 재귀적으로 선택합니다.

  • 재귀 호출이 끝난 후에는 백트래킹을 수행하여 선택한 요소를 현재 조합에서 제거합니다.

실행 결과는 다음과 같습니다.

[[1, 2], [1, 3], [2, 3]]

결과로는 주어진 배열 [1, 2, 3]에서 크기가 2인 모든 조합이 생성되었습니다. 이와 같이 백트래킹은 가능한 모든 조합을 탐색하면서 해답을 찾아내는 데에 사용됩니다.