백트래킹이란?

• 백트래킹은 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어가면서 현재 탐색 중인 상태(노드)가 제한된 조건을 위배하는지 판단하는 방식.
• 만약 해당 상태가 제한 조건을 위배한다면 즉시 탐색을 중단하고(가지치기, Pruning) 다음 가능한 상태를 탐색.
• 가장 중요한 개념:
  • 제한 조건을 위배하면 즉시 제외하고 더 깊이 탐색하지 않는다.
• 백트래킹은 모든 경우의 수를 탐색하지만 불필요한 경우를 미리 제거하여 효율성을 높임.
• 즉, 완전 탐색(Brute Force)보다 더 효율적인 탐색 기법.

백트래킹 과정

1. 현재 상태가 목표 조건을 만족하는지 확인

   • 만약 조건을 만족하면 해당 경로를 선택하고 결과 저장.
   • 예시: M개의 치킨집을 골랐을 때 최소 치킨 거리 계산.

2. 현재 상태가 유효한 상태인지 확인

   • 제한 조건을 만족하지 않으면 즉시 종료(Pruning, 가지치기).
   • 예시: 현재 선택한 치킨집 개수가 M을 초과하면 탐색 중단.

3. 다음 상태로 진행

• 가능한 모든 선택지를 하나씩 시도하면서 재귀적으로 탐색.
• 예시: 현재 선택한 치킨집을 포함하는 경우와 포함하지 않는 경우를 모두 탐색.

1. 탐색이 끝나면 이전 상태로 되돌아감 (Backtracking)
   • 현재 상태를 제거하고(백트래킹) 다른 선택지를 탐색.
   • 예시: M개를 선택한 후 다시 M-1개 상태로 돌아가 다른 조합 탐색.

예제: 조합을 이용한 백트래킹 (N개 중 M개 선택)

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> selected;

void backtrack(int start, int count) {
    if (count == M) {
        for (int num : selected) cout << num << " ";
        cout << '\n';
        return;
    }

    for (int i = start; i <= N; i++) {
        selected.push_back(i);
        backtrack(i + 1, count + 1);
        selected.pop_back(); // 백트래킹 (이전 상태로 되돌리기)
    }
}

int main() {
    cin >> N >> M;
    backtrack(1, 0);
    return 0;
}

알고리즘 설명

• N개의 숫자 중 M개를 선택하는 모든 조합을 출력.
• selected.push_back(i); → 현재 숫자를 선택.
• backtrack(i + 1, count + 1); → 다음 숫자 탐색.
• selected.pop_back(); → 백트래킹 (이전 상태로 되돌아감).

백트래킹의 핵심 개념