미로에 갇혔을 때 탈출구를 찾는 가장 확실한 방법은 깊이 우선 탐색(DFS)을 이용해 모든 길을 다 가보는 것입니다. 하지만 현실에서 무작정 모든 길을 다 가보는 것은 체력과 시간의 엄청난 낭비입니다. 만약 어떤 길로 접어들었는데 저 멀리 낭떠러지가 보인다면, 굳이 그 낭떠러지 끝까지 걸어갔다가 돌아올 바보가 있을까요? 낭떠러지가 보이는 그 즉시 발길을 돌려 다른 길을 찾는 것이 현명할 것입니다. 컴퓨터 알고리즘에서도 이처럼 "모든 경우의 수를 탐색하되, 가망이 없는 길은 조기에 포기하고 돌아온다"는 매우 효율적인 지능형 탐색 기법이 존재하는데, 이를 백트래킹(Backtracking, 퇴각 검색)이라고 부릅니다. 가지치기(Pruning)의 미학이자, 코딩 테스트 완전 탐색 파트의 끝판왕인 백트래킹의 원리와 그 유명한 'N-Queen 문제'를 완벽하게 해부해 보겠습니다.
1. 백트래킹의 개념: DFS에 지능을 더하다
백트래킹은 모든 경우의 수를 트리 형태로 펼쳐놓은 '상태 공간 트리(State Space Tree)'를 탐색하는 기법입니다. 겉보기에는 DFS와 똑같이 행동하지만, 결정적인 차이는 '유망성(Promising)' 검사와 '가지치기(Pruning)'에 있습니다.
1-1. 유망함(Promising)과 가지치기(Pruning)
DFS는 막다른 길에 도달할 때까지 무식하게 한쪽으로 파고듭니다. 정답이 없는 트리 가지의 끝자락까지 무조건 가봐야 직성이 풀리는 방식입니다.
반면 백트래킹은 어떤 노드를 방문할 때마다 먼저 "이 길이 정답으로 갈 가능성이 있는가?(Promising)"를 조건을 걸어 꼼꼼히 검사합니다. 만약 조건에 위배되어 정답이 될 가능성이 1%도 없다고 판단되면, 그 노드의 밑으로 뻗어있는 수만 개의 자식 노드들은 쳐다보지도 않고 그 즉시 탐색을 멈춘 뒤 부모 노드로 뒤로 물러나(Backtrack) 다른 자식 노드로 방향을 틀어버립니다. 이처럼 불필요한 경로를 싹둑 잘라내는 행위를 원예 용어에 빗대어 가지치기(Pruning)라고 부르며, 이를 통해 연산 횟수를 기하급수적으로 줄일 수 있습니다.
2. 백트래킹의 대명사: N-Queen 문제
백트래킹을 설명할 때 전 세계 어느 컴퓨터 공학 교재에서나 등장하는 완벽한 예시가 바로 N-Queen 문제입니다. 크기가 N x N인 체스판 위에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 경우의 수를 구하는 문제입니다. 퀸은 상하좌우, 그리고 대각선까지 모든 방향으로 거리 제한 없이 움직이며 공격할 수 있는 체스에서 가장 강력한 말입니다.
2-1. 무식한 접근(DFS)의 한계
만약 8x8 체스판(N=8)에 8개의 퀸을 아무렇게나 놓는다면, 64개의 칸 중 8개를 고르는 조합이므로 수십억 번의 경우의 수를 모두 다 탐색해야 합니다. 이는 끔찍한 비효율을 초래하며 코딩 테스트에서는 무조건 시간 초과(Time Limit Exceeded)를 발생시킵니다.
2-2. 백트래킹을 적용한 지능적 배치 시뮬레이션
백트래킹은 다음과 같은 유망성 검사 규칙을 세우고 똑똑하게 가지치기를 시작합니다.
- 첫 번째 행(Row) 규칙: 어차피 한 행에는 퀸을 하나밖에 놓지 못합니다. 가로 공격 방향이 겹치기 때문입니다. 따라서 첫 번째 줄의 1번 칸에 퀸을 일단 놓아봅니다.
- 두 번째 행 탐색: 두 번째 줄로 내려갑니다. 1번 칸에 놓으려니 바로 위 첫 번째 퀸의 '직선 공격'에 당합니다. (유망하지 않음 → 가지치기!) 2번 칸에 놓으려니 첫 번째 퀸의 '대각선 공격'에 당합니다. (유망하지 않음 → 가지치기!) 3번 칸은 안전하므로 퀸을 놓습니다.
- 퇴각(Backtrack)의 순간: 세 번째, 네 번째 줄로 계속 퀸을 놓으며 내려가다가, 어느 줄에서는 8개의 칸이 모두 위쪽 퀸들의 공격 범위에 들어가서 놓을 곳이 아예 없는 막다른 골목(Dead End)에 다다르게 됩니다.
- 이전 상태로 복구: 더 이상 퀸을 놓을 곳이 없다면, 미련 없이 이전 줄로 되돌아가서 방금 놓았던 퀸을 집어 들고 다른 안전한 칸으로 위치를 옮깁니다. 그리고 다시 다음 줄을 탐색합니다.
이처럼 백트래킹은 "놓아본다 → 유망한지 세로/대각선을 검사한다 → 막히면 방금 놓은 것을 무르고(상태 복구) 이전으로 돌아간다"는 재귀 호출의 메커니즘을 100% 활용합니다. 이 쳐내기 과정 덕분에 탐색해야 할 경우의 수는 수십억 개에서 수천 개 수준으로 극적으로 쪼그라들며 마법처럼 정답을 도출해냅니다.
1. 백트래킹(Backtracking)은 모든 경우의 수를 탐색하는 완전 탐색 과정에서, 가망이 없는 경로는 조기에 포기하고 되돌아오는 지능형 탐색 기법입니다.
2. 조건에 맞는지 확인하는 유망성(Promising) 검사와, 불필요한 탐색 공간을 날려버리는 가지치기(Pruning)가 알고리즘 성능 최적화의 핵심입니다.
3. N-Queen 문제나 스도쿠 풀이처럼 제약 조건이 명확한 복잡한 조합 문제를 풀 때 재귀 함수 구조와 결합하여 가장 강력한 힘을 발휘합니다.