[알고리즘] 백트래킹 (Backtracking)

 

 

✏️해당 포스트는 인프런 알고리즘 코딩테스트 핵심이론 강의를 토대로 정리한 내용입니다.

 

 

---

 

⭐백트래킹이란?

 

문제를 해결하는 탐색 기법을 말한다. 문제를 해결할 수 있는 모든 경로를 탐색하면서 선택한 경로가 유효하지 않거나 조건에 만족하는 해를 찾지 못할 경우, 이전 단계로 되돌아가 다른 경로를 시도하는 알고리즘 

 

즉 다시 정리하자면, 해(정답)를 찾기 위해 모든 경우의 수를 탐색하되, 탐색 도중에 해가 될 수 없는 경우(불필요한 경로) 를 만나면 더 이상 진행하지 않고 되돌아가(backtrack) 다른 경로를 시도하는 탐색 기법.

 

 

구현 방식

• 재귀 함수로 구현하는 경우가 많음. (DFS의 개념과 구현방식이 매우 유사, 다만 DFS는 모든 노드를 탐색하는 것을 목적으로 함) 
• 가지치기(pruning)를 통해 불가능한 경우는 일찍 포기 → 효율 상승 
• 각 단계에서 가능한 선택지를 반복하면서:
  1. 현재 선택이 유효한지 검사
  2. 유효하다면 다음 단계로 재귀 호출
  3. 해를 찾거나 막히면 → 다시 돌아와 다른 선택 시도 

 

백트래킹을 활용할 수 있는 대표적인 문제

• 조합
• 순열
• N-Queens 문제 

 

 

코딩 테스트에서 DFS로 문제를 해결하는 문제 역시 대부분 성능향상을 위해 가지치기를 사용한다   

 

 

⭐백트래킹 핵심 이론 

 

 

문제를 해결하기 위한 가능한 경로를 탐색하며 조건을 만족하지 않는 경로를 가지치기하여 탐색 범위를 줄이는 것이 핵심 

 

 

 

주어진 수 조합을 모두 더한 것이 50이 되는 경우의 수를 구한다면?  (데이터는 자연수 )

 

• 입력: 자연수 배열 nums[]
• 목표: 부분집합(조합)을 골라서 합이 50이 되는 경우의 수 세기

즉, 각 숫자를 선택하거나 선택하지 않거나 두 갈래로 뻗어나가는 트리 탐색 문제 → 백트래킹으로 해결.

 

public class Main {
    static int count = 0; // 경우의 수 저장
    static int[] nums = {10, 20, 30, 25, 5, 15}; // 예시 데이터

    public static void main(String[] args) {
        backtrack(0, 0);
        System.out.println("경우의 수: " + count);
    }

    // idx = 현재 위치, sum = 지금까지의 합
    static void backtrack(int idx, int sum) {
        // 1. 합이 50 초과 → 더 이상 볼 필요 없음
        if (sum > 50) return;

        // 2. 모든 숫자 다 확인했을 때
        if (idx == nums.length) {
            if (sum == 50) count++;
            return;
        }

        // 3. 현재 숫자 선택하는 경우
        backtrack(idx + 1, sum + nums[idx]);

        // 4. 현재 숫자 선택하지 않는 경우
        backtrack(idx + 1, sum);
    }
}

 

 

start (idx=0, sum=0)
 ├── [10 선택] → (idx=1, sum=10)
 │     ├── [20 선택] → (idx=2, sum=30)
 │     │      ├── [30 선택] → (idx=3, sum=60) 
 │     │      └── [30 선택X] → (idx=3, sum=30) 
 │     └── [20 선택X] → (idx=2, sum=10)
 │            ├── [30 선택] → (idx=3, sum=40)
 │            └── [30 선택X] → (idx=3, sum=10)
 └── [10 선택X] → (idx=1, sum=0)
       ├── [20 선택] → (idx=2, sum=20)
       │      ├── [30 선택] → (idx=3, sum=50)
       │      └── [30 선택X] → (idx=3, sum=20)
       └── [20 선택X] → (idx=2, sum=0)
              ├── [30 선택] → (idx=3, sum=30)
              └── [30 선택X] → (idx=3, sum=0)

 

 

 

 

백트래킹 간단한 코드 

back(sum) {
    if (sum == 50) {
        cnt++; // 정답 하나 찾음
        return;
    }

    for (Now : numbers) {
        if (Now + sum <= 50) {   // 가지치기
            sum += Now;          // 선택
            back(sum);           // 재귀
            sum -= Now;          // 선택 취소 (되돌리기)
        }
    }
}