"답이 아닌 것 같으면 즉시 돌아가서 다른 길을 탐색하는 스마트한 완전 탐색"
백트래킹이란?
백트래킹(Backtracking)은
모든 경우를 시도하되,
"이 경로는 답이 될 수 없다"라고 판단되면
바로 중간에 포기하고 되돌아가는(Back) 알고리즘입니다.
브루트포스(완전 탐색)를 더 효율적으로 개선한 형태라고 볼 수 있습니다.
- 일단 가능한 선택을 따라 내려가면서 탐색합니다.
- 중간에 잘못된 선택이라고 판단되면, 다시 이전 상태로 돌아갑니다.
- 돌아가면서 다른 선택을 다시 탐색합니다.
주요 키워드
- "선택(Choice)"
- "탐색(Explore)"
- "포기(Abandon)"
- "되돌아가기(Backtrack)"
백트래킹이 필요한 이유
완전 탐색(Brute Force)은 단순하지만, 가능한 모든 경우를 끝까지 가보려 합니다.
하지만 경우의 수가 너무 많아지면 현실적으로 불가능합니다.
백트래킹은 이런 상황을 해결합니다.
| 구분 | 설명 |
| 경우의 수가 많을 때 | 불필요한 경우를 조기에 제거 |
| 효율적으로 탐색할 때 | 답이 될 수 없는 경로는 즉시 버림 |
| 최적화된 정답이 필요할 때 | 가장 빠르게 답에 도달 가능 |
즉, 가능성이 없는 길은 아예 탐색하지 않기 때문에 시간과 자원을 아낄 수 있습니다.
백트래킹 기본 동작 원리
흐름
- 현재 경로를 선택한다.
- 조건을 확인한다.
- 조건을 만족하지 않으면 즉시 돌아간다 (Prune).
- 조건을 만족하면 더 깊이 탐색한다.
- 최종 목표에 도달하면 결과를 저장한다.
- 다른 경로를 탐색하기 위해 한 단계 되돌아간다(Backtrack).
기본 코드 구조 (Python 예시)
def backtrack(path, options):
if end_condition(path):
result.append(path)
return
for option in options:
if valid(option, path):
path.append(option)
backtrack(path, options)
path.pop() # 되돌아가기path: 현재까지 선택한 경로options: 선택할 수 있는 후보valid(): 유효성 검사end_condition(): 탐색 종료 조건path.pop(): Backtracking 핵심, 한 단계 이전으로 돌아감
백트래킹 알고리즘 패턴
백트래킹은 다양한 형태로 등장합니다.
순열 생성
N개의 원소로 만들 수 있는 모든 순서를 찾는 문제
조합 생성
N개의 원소 중 K개를 선택하는 모든 방법
부분 집합(Subsets)
주어진 집합의 모든 부분 집합 찾기
조건부 경로 탐색
미로 찾기, 체스판 문제 (예: N-Queens), 퍼즐 풀이
백트래킹의 장단점
장점
| 항목 | 설명 |
| 불필요한 계산을 줄인다 | 조건을 이용해 중간에 탐색을 멈춘다 |
| 복잡한 문제를 풀 수 있다 | 순열, 조합, 경로 문제 등 |
| 결과가 항상 정확하다 | 모든 가능성 탐색을 보장 |
단점
| 항목 | 설명 |
| 여전히 최악의 경우 지수 시간 | 조건이 약하면 사실상 완전 탐색과 같음 |
| 구현이 까다로울 수 있다 | 복잡한 유효성 검사와 조건 관리 필요 |
대표 문제 예시
N-Queens 문제
- N × N 체스판에 N개의 퀸을 서로 공격하지 않게 배치하는 방법
숫자 조합 문제
- 주어진 숫자 배열에서 합이 특정 값이 되는 모든 조합을 찾기
미로 찾기 (Maze Solving)
- 출발점에서 도착점까지 이동할 수 있는 모든 경로를 찾기
Sudoku Solver
- 주어진 스도쿠 퍼즐을 올바르게 채우는 방법 찾기
백트래킹 최적화 기법 (가지치기)
백트래킹을 더 빠르게 만들기 위해 Pruning(가지치기) 기술을 많이 사용합니다.
가지치기 방법
- 사전 유효성 검사(Pre-Check)
선택하기 전에 조건을 먼저 검사해서 불필요한 시도를 제거 - 최적화 조건 추가(Early Stopping)
목표를 달성하거나 조건을 만족하면 바로 중단 - 정렬 후 탐색(Optimization by Ordering)
탐색 순서를 조정해서 더 빨리 조건에 도달하게 만들기
가지치기 예시 (N-Queens 문제)
def is_valid(board, row, col):
for i in range(row):
if board[i] == col or abs(board[i] - col) == abs(i - row):
return False
return True
def solve(board, row, n):
if row == n:
result.append(board[:])
return
for col in range(n):
if is_valid(board, row, col):
board[row] = col
solve(board, row + 1, n)
board[row] = -1 # 백트래킹is_valid로 유효성 검사를 미리 하고- 실패할 가능성이 높은 경로를 아예 탐색하지 않습니다.
마무리 요약
| 항목 | 요약 |
| 백트래킹 정의 | 가능한 선택을 시도하다가 틀리면 즉시 되돌아가는 알고리즘 |
| 강점 | 중간에 불필요한 계산 줄이기, 복잡한 문제 해결 |
| 약점 | 최악의 경우 완전 탐색 수준, 구현 난이도 있음 |
| 대표 문제 | N-Queens, 미로찾기, 스도쿠, 조합/순열 생성 |
| 최적화 방법 | 가지치기(Pruning), 정렬, 사전 조건 검사 |
728x90