[Algorithm/Study] 7주차 - 백트래킹

 

해당 스터디는 <코딩 테스트 합격자 되기 C++> 저자님과 함께하는 스터디입니다.

인프런 강의 < 코딩 테스트 합격자 되기 C++ > 을 보고 정리한 내용입니다.

---

백트래킹이란?

💡 백트래킹 : 가장 최근에 방문했던 노드로 다시 돌아가는 것(ex. DFS), 완전 탐색X 내가 찾는 답일 가능성이 있는 경우에만 탐색

 

외출을 했는데 집에 물건을 놓고 왔을 경우, 모든 아파트를 탐색해야 할까? 그런 사람은 없을 것이다.🤔 당연히 우리집에 물건을 놓고왔으니, 다른집에는 물건이 없다고 판단한다. 이 부분을 구현해야 하는 것이고, 이것을 유망함수라고 한다. 다른집에 있을 가능성이 없다(=유망하지 않다)는 것을 표현하는 것을 말한다.

 

✔️ 상태 정의 : 문제의 각 단계에서 가능한 상태를 정의하는 것

✔️ 유망함수(isPromising) : 현재 상태가 유망한지 판단하고, 유망하지 않으면 더 이상 탐색하지 않는 것

✔️ 해결책 확인(isSolution) : 현재 상태가 문제의 해결책인지 판단하는 것

✔️ 재귀 호출 : 유망한 상태로 이동하면서 문제를 해결하는 것(유망하면 계속해서 재귀호출을 통해 탐색, 즉 DFS 진행)

 

백트래킹의 기본적인 구조는 다음과 같다. 머리 속에 구조를 넣어두자!

public class BacktrackingTemplate {

    // 유망성 판단 함수
    private boolean isPromising(int level, State state) {
        // 현재 상태가 유망한지 판단하는 로직을 구현
    }

    // 해결책 확인 함수
    private boolean isSolution(State state) {
        // 현재 상태가 문제의 해결책인지 판단하는 로직을 구현
    }

    // 해결책 처리 함수
    private void processSolution(State state) {
        // 해결책을 처리하는 로직을 구현 (예: 출력)
        System.out.println(state);
    }

    // 백트래킹 함수
    private void backtrack(int level, State state) {
        // 현재 상태가 해결책이면 처리
        if (isSolution(state)) {
            processSolution(state);
            return;
        }

        // 다음 가능한 상태를 탐색
        for (State nextState : state.possibleStates()) {
            if (isPromising(level, nextState)) {
                backtrack(level + 1, nextState); // 재귀 호출
            }
        }
    }

    public static void main(String[] args) {
        // 초기 상태 설정
        State initialState = new State();
        BacktrackingTemplate bt = new BacktrackingTemplate();

        // 백트래킹 시작
        bt.backtrack(0, initialState);
    }
}

백트래킹 예시

부분합

❔ {1, 2, 3, 4}로 이루어진 집합에서 숫자를 뽑아 합이 5인 조합을 구하는 문제

• 완전탐색으로도 풀 수 있지만, 시간복잡도 O(2^N)으로 효율적이지 않다.
• 백트래킹으로 접근해 더 효율적으로 풀 수 있다.
  • 상태 정의 : 현재까지 선택한 숫자들의 합
  • 유망함수 : 현재 부분 합이 목표 값을 초과하면 유망하지 않다고 판단
  • 해결책 확인 : 현재 부분 합이 목표 값과 일치하는지 확인
  • 재귀 호출 : 다음 숫자를 선택하여 부분합 갱신

import java.util.*;

public class SubsetSum {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4}; 
        int target = 5; // 목표 합
        List<List<Integer>> result = new ArrayList<>();

        // 백트래킹 시작
        findCombinations(numbers, 0, target, new ArrayList<>(), result);

        // 결과 출력
        System.out.println("합이 5가 되는 조합:");
        for (List<Integer> combination : result) {
            System.out.println(combination);
        }
    }
    
    private static void findCombinations(int[] numbers, int index, int target, List<Integer> current, List<List<Integer>> result) {
        // 종료 조건: 목표 합에 도달한 경우
        if (target == 0) {
            result.add(new ArrayList<>(current)); // 현재 조합을 결과에 추가
            return;
        }

        // 탐색 범위 초과 또는 목표 초과
        if (target < 0 || index >= numbers.length) {
            return;
        }

        // 현재 원소를 포함
        current.add(numbers[index]);
        findCombinations(numbers, index + 1, target - numbers[index], current, result);
        current.remove(current.size() - 1); // 백트래킹

        // 현재 원소를 포함하지 않음
        findCombinations(numbers, index + 1, target, current, result);
    }
}