백트래킹 (Backtracking)

한 줄 정의: 가능한 선택지를 하나씩 시도해보다가 더 이상 답이 될 수 없다고 판단되면 그 선택을 취소하고 이전 단계로 되돌아가, 다른 경로를 다시 시도하는 방식으로 해를 찾는 탐색 기법입니다.

쉽게 풀면

미로를 탐험한다고 생각해봅시다. 갈림길이 나올 때마다 한 방향을 골라 계속 걸어가다가, 막다른 벽에 부딪히면 그 자리에서 포기하는 게 아니라 바로 직전 갈림길까지 되돌아가서 아직 가보지 않은 다른 방향을 시도합니다. 백트래킹은 바로 이 "가보고, 막히면 되돌아가서 다른 길을 시도하는" 과정을 알고리즘으로 옮긴 것입니다. 가능한 모든 조합을 무작정 다 만들어보는 완전탐색과 달리, 지금까지의 선택이 조건에 이미 어긋난다는 게 확인되면 그 뒤를 더 파고들지 않고 즉시 되돌아가기 때문에 불필요한 계산을 크게 줄일 수 있습니다.

왜 중요한가

많은 실무 문제는 "가능한 모든 경우를 다 확인하면 답은 찾을 수 있지만, 경우의 수가 너무 많아 현실적으로 불가능하다"는 딜레마를 안고 있습니다. 백트래킹은 이런 완전탐색 문제에서 조건에 어긋나는 경로를 최대한 일찍 잘라내어 실제로 확인해야 하는 경우의 수를 줄이는 가장 기본적인 전략이기 때문에, 제약 충족 문제(CSP), 조합 최적화, 계획 수립(planning), 자동 정리 증명 등 다양한 인공지능·알고리즘 연구에서 기준 기법(baseline) 혹은 더 정교한 탐색·최적화 기법의 출발점으로 자주 등장합니다. 또한 백트래킹으로 문제를 얼마나 효율적으로 풀 수 있는지는 해당 문제의 구조(제약 간 상호작용, 대칭성 등)를 얼마나 잘 활용했는지를 보여주는 척도가 되기도 합니다.

논문에서는 이렇게 쓰입니다

"제약 조건을 만족하는 배치를 찾기 위해 백트래킹(backtracking) 기반 탐색을 적용하였으며, 조건 위반이 확인되는 즉시 가지치기(pruning)를 수행하여 탐색 공간을 크게 줄였다."

이 문장은 스도쿠, 그래프 색칠, 순열·조합 생성처럼 조건을 만족하는 답을 찾아야 하는 문제에서, 잘못된 경로임이 확인되면 그 경로를 더 이상 탐색하지 않고 즉시 이전 단계로 돌아감으로써 확인해야 할 경우의 수 자체를 줄였다는 뜻입니다. 제약 충족 문제, 조합 최적화, 인공지능 탐색 논문에서 널리 쓰입니다.

"본 연구에서는 SAT 솔버의 핵심 절차로 백트래킹 탐색에 충돌 기반 절 학습(conflict-driven clause learning)을 결합하여, 단순 백트래킹 대비 탐색 실패 횟수를 크게 줄였다."

이 문장은 논리식의 충족 가능성을 판단하는 SAT(Boolean satisfiability) 문제에서, 기본적인 백트래킹만 쓰는 대신 이전에 실패한 이유를 기록해두었다가 이후 탐색에서 같은 실패를 반복하지 않도록 개선한 기법을 적용했다는 뜻입니다. 백트래킹은 이처럼 더 발전된 탐색 알고리즘의 뼈대로도 자주 인용됩니다.

"로봇 팔의 경로 계획 문제에서 충돌이 발생하는 구간까지 도달하면 이전 분기점으로 백트래킹하여 대안 경로를 탐색하는 방식으로 실행 가능한 경로를 생성하였다."

이 문장은 로봇공학의 경로 계획(path planning) 분야에서, 장애물과 충돌하는 경로가 확인되면 그 지점에서 곧바로 되돌아가 다른 분기를 시도함으로써 실행 가능한 경로를 찾아냈다는 뜻입니다. 이처럼 백트래킹은 순수 알고리즘 이론뿐 아니라 로봇공학, 자연어 파싱, 컴파일러의 구문 분석 등 실무적인 탐색 문제에서도 폭넓게 쓰입니다.

조금 더 깊게 보면

백트래킹을 다루는 논문을 읽을 때 함께 등장하는 핵심 개념이 가지치기(pruning) 전략입니다. 단순히 막다른 길에서 되돌아가는 것을 넘어, 지금까지의 선택만으로 앞으로도 답이 나올 수 없음을 미리 판단해 아예 그 가지(branch)를 탐색하지 않는 것이 성능을 좌우합니다. 이런 가지치기를 언제, 어떻게 적용하느냐에 따라 분기한정법(branch and bound)처럼 탐색 중간에 상한·하한을 계산해 더 적극적으로 가지를 쳐내는 변형들이 파생되며, 제약 충족 문제에서는 변수·값을 선택하는 순서를 조정하는 휴리스틱(예: 남은 후보가 적은 변수부터 시도)도 함께 논의됩니다. 성능을 비교할 때는 대체로 실행 시간이나 확인한 노드(탐색한 경우의 수) 개수를 지표로 사용하는 경우가 많습니다.

주의할 점

백트래킹은 완전탐색보다 빠르지만 여전히 최악의 경우에는 지수적으로 많은 경우의 수를 확인해야 할 수 있어, 문제 규모가 커지면 동적계획법이나 탐욕 알고리즘 같은 다른 접근이 더 적합할 수 있습니다. 어떤 문제에 어떤 기법이 맞는지는 부분 문제가 겹치는지, 매 순간의 최선 선택이 전체 최선으로 이어지는지 등 문제의 구조를 먼저 살펴본 뒤 판단해야 합니다.