백트래킹(Backtracking)은 가능한 모든 후보 해(solution)를 탐색하는 과정에서, 조건에 맞지 않는 불필요한 경로를 미리 차단(가지치기, pruning)하여 효율적으로 해답을 찾는 알고리즘 기법이다.

기본 개념

• 재귀적 탐색: 문제를 여러 단계의 결정(decision)으로 분해하고, 각 단계에서 가능한 선택지를 하나씩 시도한다. 재귀 호출을 통해 해답의 한 부분씩 구축해 나가다가 조건에 위배되면 이전 단계로 돌아간다.
• 가지치기(Pruning): 현재까지의 선택이 문제의 조건에 어긋난다고 판단되면, 더 이상의 탐색을 중단하고 이전 상태로 돌아가는 방식이다. 이를 통해 전체 탐색 공간을 줄이고 효율성을 높일 수 있다.

동작 원리

1. 해의 후보 구성: 예를 들어, 순열, 조합, 혹은 미로 찾기와 같은 문제에서 각 단계마다 선택 가능한 후보를 나열
2. 조건 확인: 현재까지의 선택이 문제의 조건(제약 조건)을 만족하는지 확인
3. 재귀적 진행: 조건을 만족한다면, 다음 단계로 진행하며 추가적인 선택을 시도
4. 백트래킹: 만약 현재의 선택이 조건을 위반하거나 더 이상 진행해도 올바른 해답에 도달할 수 없다고 판단되면, 마지막으로 선택한 항목을 취소(백트랙)하고 다른 후보를 시도

예시

• N-Queen 문제: 체스판에 서로 공격하지 않는 N개의 퀸을 배치하는 문제에서, 한 행마다 하나의 퀸을 배치하는 방식으로 진행한다. 만약 특정 배치가 서로 공격 가능하면, 해당 경로를 포기하고 다른 배치를 시도한다.
• 미로 찾기: 미로에서 출발점부터 도착점까지의 경로를 찾는 문제에서, 각 방향으로 이동하며 경로가 막히면 이전 위치로 돌아가 다른 경로를 탐색한다.

장점과 단점

• 장점:
  • 모든 경우의 수를 고려하지만, 불필요한 경로를 일찍 차단하여 효율적으로 탐색할 수 있다.
  • 문제의 구조를 단계별로 나눌 수 있다면 구현이 직관적이다.
• 단점:
  • 최악의 경우 모든 후보를 탐색해야 하므로 경우의 수가 매우 많으면 성능이 떨어질 수 있다.
  • 가지치기 조건을 잘 설정하지 않으면 여전히 비효율적일 수 있다.

백트래킹은 [[ 완전 탐색 ]]의 한 형태지만, 조건에 따라 불필요한 부분을 미리 배제함으로써 실제로는 훨씬 빠른 탐색이 가능해집니다. 이러한 특성 덕분에 조합, 순열, 퍼즐 문제 등 다양한 문제에서 자주 활용됩니다.

참고

• ChatGPT(o3-mini-high)