백트래킹(Backtracking) — 완전탐색을 효율적으로 만드는 방법

1. 백트래킹의 개념

백트래킹(Backtracking)은 모든 가능한 경우의 수를 탐색하면서, 불필요한 경로를 조기에 차단하는 탐색 알고리즘이다.
쉽게 말해 “조건에 맞지 않으면 바로 돌아가는(Backtrack)” 방식의 완전탐색이다.

완전탐색(Brute-force)은 가능한 모든 경우를 시도하기 때문에, 경우의 수가 많을수록 계산량이 급격히 늘어난다.
하지만 백트래킹은 탐색 도중 “이 경로로 가도 정답이 될 수 없다”는 판단이 내려지면 그 즉시 탐색을 중단하고 이전 단계로 돌아간다.
이 과정을 반복하면서 필요한 경로만 탐색하게 되어 시간 복잡도를 크게 줄일 수 있다.

---

2. 백트래킹의 동작 방식

백트래킹은 기본적으로 DFS(깊이 우선 탐색) 형태로 동작한다.
탐색 도중 조건을 만족하지 않으면 즉시 되돌아가며, 이를 위해 다음과 같은 구조를 갖는다.

1. 결정(Choose)

   • 현재 단계에서 하나의 선택을 수행한다.
   • 예: 수 하나를 선택, 퀸을 배치, 연산자를 사용 등

2. 탐색(Explore)

   • 해당 선택을 기준으로 재귀적으로 다음 단계로 이동한다.

3. 복원(Unchoose)

   • 다음 단계로 진행 후 다시 돌아올 때, 이전 선택을 원래 상태로 되돌린다.
   • 이를 통해 다른 가능한 선택지를 탐색할 수 있게 된다.

이 세 단계가 재귀적으로 반복되며, 최종적으로 모든 가능한 조합이 만들어진다.
핵심은 “가능하지 않은 선택은 더 이상 진행하지 않는다”는 점이다.

---

3. 백트래킹의 적용 방법

백트래킹을 적용할 때는 다음 세 가지를 명확히 정의해야 한다.

1. 탐색 대상 (state)

   • 어떤 상태를 기준으로 탐색을 진행할지 정의
   • 예: 현재 위치, 선택된 수열, 배치된 퀸 개수 등

2. 유효성 검사 (constraint check)

   • 현재 상태가 조건을 만족하는지 판단
   • 조건을 만족하지 않으면 즉시 탐색 중단 (pruning)

3. 종료 조건 (termination)

   • 탐색이 끝나는 시점을 명확히 정의
   • 예: 조합의 길이가 6이 되었을 때, 모든 퀸이 배치되었을 때 등

이 세 가지가 정의되면 백트래킹 알고리즘의 기본 구조는 자연스럽게 만들어진다.

---

4. 문제별 백트래킹 적용

아래 세 문제를 통해 백트래킹의 실제 활용 방식을 정리했다.

---

(1) 로또 — 조합 생성

문제 개요

주어진 집합 S에서 6개의 수를 고르는 모든 조합을 출력하는 문제.

백트래킹 적용 방식

• 탐색 대상: 현재 선택된 숫자 조합
• 유효성 검사: 남은 숫자의 개수가 부족하면 탐색 중단
• 종료 조건: 6개 숫자를 모두 선택했을 때 출력

if (k - pos - 1 < 6 - depth) return; // 남은 숫자가 부족하면 중단

백트래킹의 핵심은 가능한 조합만 탐색하도록 가지치기를 수행한 것이다.
남은 원소가 부족하면 더 이상 조합이 완성될 수 없기 때문에, 그 시점에서 재귀 호출을 중단한다.

이를 통해 완전탐색이지만, 불필요한 분기는 제거된 조합 탐색이 가능하다.

---

(2) N-Queen — 상태 제약 기반 탐색

문제 개요

N×N 체스판 위에 N개의 퀸을 서로 공격하지 않게 배치하는 경우의 수를 구하는 문제.

백트래킹 적용 방식

• 탐색 대상: 현재 행(row)에 퀸을 배치할 열(col)
• 유효성 검사: 해당 위치가 공격 가능한 위치인지 확인
• 종료 조건: 모든 행에 퀸이 배치되었을 때 결과 증가

if (chess[row][col] == 0) {
    placeQueen(row, col);
    backtracking(row + 1);
    removeQueen(row, col);
}

백트래킹의 핵심은 상태 관리이다.
chess 배열을 이용해 공격 가능한 칸을 숫자로 표시하고, 퀸을 배치하거나 제거할 때 해당 영역을 동적으로 갱신한다.

이 과정을 통해 “공격 가능한 위치는 탐색하지 않는다”는 pruning이 자연스럽게 적용된다.
즉, 탐색 가능한 영역을 실시간으로 줄여나가는 형태의 백트래킹이다.

---

(3) 연산자 끼워넣기 — 선택 순서 탐색

문제 개요

주어진 수열 사이에 연산자를 끼워 넣어 만들 수 있는 결과값의 최대값과 최소값을 구하는 문제.

백트래킹 적용 방식

• 탐색 대상: 현재까지 계산된 식의 값
• 유효성 검사: 사용 가능한 연산자의 개수가 남아 있는지 확인
• 종료 조건: 모든 수를 사용했을 때 결과 비교 및 갱신

operators[i]--;
backtracking(depth + 1, newValue);
operators[i]++;

연산자를 선택하고, 재귀적으로 다음 연산을 수행한 뒤, 돌아올 때 다시 복원한다.
이 과정에서 상태 복원(Unchoose)이 핵심이며, 이를 통해 모든 가능한 연산자 조합을 완전탐색할 수 있다.

---

5. 백트래킹의 핵심 정리

단계	내용
1	가능한 선택지를 시도
2	조건을 만족하지 않으면 되돌아감 (Pruning)
3	조건을 만족하면 재귀적으로 다음 단계 탐색
4	종료 조건을 만나면 결과 저장
5	돌아올 때 상태를 복원하여 다른 경우 탐색

세 문제 모두 이 패턴을 그대로 따른다.
로또는 “조합의 깊이”, N-Queen은 “위치의 유효성”, 연산자 끼워넣기는 “상태 복원”을 중심으로 백트래킹을 구성했다.

---

6. 결론

백트래킹은 완전탐색과 유사하지만, 조건 기반 가지치기를 통해 효율을 확보하는 탐색 알고리즘이다.
즉, 가능한 모든 해를 시도하면서도 불필요한 계산을 피한다는 점에서 차별화된다.

문제를 풀 때는 다음 질문을 기준으로 접근하면 된다.

1. 어떤 상태를 기준으로 탐색을 진행할 수 있는가?
2. 어떤 조건에서 탐색을 중단할 수 있는가?
3. 탐색이 끝났다는 것은 어떤 상태를 의미하는가?

이 세 가지를 명확히 정의할 수 있다면, 어떤 문제든 백트래킹으로 접근할 수 있다.
로또, N-Queen, 연산자 끼워넣기 세 문제는 이러한 사고 과정을 훈련하기에 적합한 대표적인 예시다.