백트래킹(Backtracking)

백트래킹(Backtracking)

백트래킹은 모든 가능한 경우의 수를 탐색하면서, 조건에 맞지 않는 경로는 탐색을 중단하고 이전 단계로 돌아가는 기법입니다. 재귀 호출을 통해 동적으로 탐색 깊이를 조절할 수 있다는 점이 가장 큰 특징입니다.

DFS기반

---

백트래킹의 핵심 요소

1. 완전탐색

• 가능한 모든 선택지를 시도하며, 최적의 해를 찾거나 특정 조건을 만족하는 해를 구합니다.
• 예를 들어, 미로 탐색에서는 모든 경로를 탐색해 최단 경로를 찾습니다.

 

2. Pruning(가지치기)

• 조건을 만족하지 않는 경로는 더 이상 탐색하지 않고 조기에 종료합니다.
• 이를 통해 탐색 시간을 줄이고 효율성을 높입니다.

 

3. 동적 깊이 조절

• 백트래킹은 재귀 호출을 사용하기 때문에 탐색 깊이를 문제 상황에 따라 동적으로 변경할 수 있습니다.
• 이는 깊이가 고정된  for 루프와의 가장 큰 차이점입니다.

---

for 루프와 백트래킹의 차이 : 동적 깊이

for 루프의 한계

for루프는 탐색 깊이가 미리 정해져 있어야 합니다.

예를 들어, 깊이 3의 조합을 탐색하려면 다음과 같이 고정된 코드를 작성하면 됩니다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            // 깊이 3에서 수행할 작업
        }
    }
}

 

문제점 : 깊이가 가변적인 경우 대응할 수 없습니다.

 

---

백트래킹 요소

백트래킹 공식처럼 파악해야할 요소들을 정리하면 다음과 같습니다.

1. 문제의 특성 파악

백트래킹은 다음과 같은 문제에서 적합합니다.

• 모든 가능한 조합을 탐색해야 하는 경우
  • 예 : 순열/ 조합 생성
• 조건을 만족하는 최적의 해를 찾아야 하는 경우
  • 예 : 그래프의 최단 경로 탐색
• 탐색 깊이가 동적으로 결정되는 문제
  • 예 : 그래프 경로 탐색, 조합 문제
• 결과가 여러 개 존재할 수 있는 경우
  • 예 : 모든 가능한 해를 출력해야 하는 문제
  •  

---

2. 문제 정의 및 파악

2-1. 탐색 공간(Solution Space)

가능한 모든 선택지를 정의합니다

-  예 : 순열 문제에서 가능한 숫자 리스트

 

2-2. 종료 조건(Termination condition)

탐색을 멈춰야 할 조건을 명확히 정의합니다.

-  예 : 원하는 깊이(레벨)에 도달했을 때, 현재 상태가 해답 조건을 만족할 때

 

2-3. 가지치기 조건(Pruning Condition)

탐색을 중단해야 하는 상황을 정의합니다.

-  예 : 경로 탐색 문제에서 이미 현재 경로가 최적보다 나쁜 경우

 

2-4. 결과 저장 방법

해답을 저장하는 방식을 결정합니다.

-  단일 해답 : 최적의 값 하나를 저장

-  다중 해답 : 조건을 만족하는 모든 해를 저장

---

3. 백트래킹을 구현하기 위한 공식적 요소

void backtrack(현재 상태 변수들) {
    // 1. 종료 조건
    if (탐색을 종료할 조건) {
        결과 저장 또는 계산;
        return;
    }

    // 2. 가능한 선택지 반복
    for (가능한 선택지 : 선택지 목록) {
        if (가지치기 조건) continue; // 조건을 만족하지 않으면 건너뛰기

        // 3. 선택(상태 변경)
        상태 갱신;

        // 4. 재귀 호출(다음 단계로 이동)
        backtrack(다음 상태 변수들);

        // 5. 선택 해제(상태 복구) => 백트래킹
        상태 복구;
    }
}

3-1. 종료 조건(Termination Condition)

탐색을 멈춰야 할 조건을 정의합니다.

• 탐색이 완료되었음을 나타냅니다.
• 예:
  • 탐색 깊이가 최대 깊이에 도달한 경우: if (depth == maxDepth).
  • 모든 요소를 선택한 경우: if (current.size() == n).
  • 특정 값(목표)을 찾은 경우: if (currentSum == target).

---

3-2. 가지치기 조건(Pruning Condition)

탐색 트리에서 유망하지 않은 경로를 조기에 중단합니다.

• 효율성을 높이기 위한 핵심 요소입니다.
• 예:
  • N-Queens: 같은 열 또는 대각선에 퀸이 있으면 중단.
  • 경로 탐색: 현재 합계가 목표 값을 초과하면 중단.

---

3-3. 선택과 상태 갱신

현재 상태에서 가능한 모든 선택지를 탐색합니다.

• 선택 후, 상태를 갱신하여 다음 단계로 이동합니다.
• 예:
  • 숫자를 선택해 현재 조합에 추가: current.add(nums[i]).
  • 현재 합계 갱신: currentSum += nums[i].
  • 노드를 방문 처리: visited[i] = true.

---

3-4. 재귀 호출

선택한 상태를 기반으로 다음 단계를 탐색합니다.

• 재귀적으로 탐색하며, 탐색 깊이는 재귀 호출의 깊이로 표현됩니다.
• 예:
  • 다음 인덱스로 이동: backtrack(index + 1, ...).
  • 그래프의 다음 노드 탐색: backtrack(nextNode, ...).

---

3-5. 선택 해제(상태 복구)

현재 상태를 복구하여 다른 선택지를 시도합니다.

• 필수 작업: 선택한 상태를 취소하지 않으면 다음 탐색에 영향을 줍니다.
• 예:
  • 현재 조합에서 숫자를 제거: current.remove(current.size() - 1).
  • 방문 여부 초기화: visited[i] = false.
  • 합계 복구: currentSum -= nums[i].

 

 

예제

최적의 조합찾기

public class Solution {
    static int[][] ability; // 능력치 배열
    static boolean[] used; // 사용 여부 체크
    static int maxSum;     // 최대 합계 저장

    public static int solution(int[][] inputAbility) {
        ability = inputAbility;
        int people = ability.length;
        int sports = ability[0].length;

        used = new boolean[people]; // 초기화
        maxSum = 0; // 최대값 초기화

        // 백트래킹 시작
        backtrack(0, 0, sports);

        return maxSum;
    }

    private static void backtrack(int sportIndex, int currentSum, int sports) {
        // 모든 종목에 대해 사람을 선택한 경우
        if (sportIndex == sports) {
            maxSum = Math.max(maxSum, currentSum); // 최대값 갱신
            return;
        }

        // 현재 종목에 대해 가능한 모든 사람 선택
        for (int person = 0; person < ability.length; person++) {
            if (!used[person]) { // 아직 사용되지 않은 사람만 선택
                used[person] = true; // 선택
                backtrack(sportIndex + 1, currentSum + ability[person][sportIndex], sports); // 다음 종목으로 이동
                used[person] = false; // 선택 해제 (백트래킹)
            }
        }
    }

    public static void main(String[] args) {
        // 예제 입력
        int[][] inputAbility = {
            {40, 10, 10},
            {20, 5, 0},
            {30, 30, 30},
            {70, 0, 70},
            {100, 100, 100}
        };

        // 결과 출력
        int result = solution(inputAbility);
        System.out.println("최대 합계: " + result); // 예상 출력: 210
    }
}