백트래킹(Backtracking) 알고리즘

개요

백트래킹(Backtracking)은 가능한 모든 경우의 수를 탐색하되, 불가능하거나 의미 없는 경로는 조기에 차단(pruning)하는 완전 탐색 기법이다. DFS(깊이 우선 탐색)를 기반으로 하며, 부분 해(partial solution)를 점진적으로 구성해가다가 해답이 아니라고 판단되면 직전 상태로 되돌아가 다른 경로를 탐색한다. 퍼즐, 조합, 순열, 경로 탐색 등 다양한 문제에 사용된다.

---

1. 개념 및 정의

• 완전 탐색(Brute Force): 가능한 모든 경우를 시도
• 백트래킹: 모든 경우를 시도하되, 유망하지 않은 경로는 가지치기(prune)
• 재귀 호출 + 조건 기반 되돌아가기 형태로 구현됨

---

2. 동작 구조

단계	설명
1	현재 노드(상태)가 해답인지 확인
2	해답이면 출력 또는 저장
3	아니라면 다음 가능한 선택지로 이동
4	조건에 맞지 않거나 끝에 도달하면 되돌아감

재귀 호출 + 조건 분기로 구성되는 것이 특징이다.

---

3. 대표 문제 예시

문제	설명
N-Queen 문제	퀸들이 서로 공격하지 않도록 배치 (행, 열, 대각선 가지치기)
순열/조합 생성	중복 없이 또는 조건에 맞는 순열/조합 생성
미로 찾기	출발점부터 도착점까지 모든 경로 탐색
부분집합(Subset)	전체 집합의 가능한 부분집합 구하기
Sudoku	9x9 숫자 퍼즐 채우기

---

4. 파이썬 예시 (N-Queen)

def is_safe(board, row, col, n):
    for i in range(row):
        if board[i] == col or abs(board[i] - col) == row - i:
            return False
    return True

def solve_n_queens(n, board=[], row=0):
    if row == n:
        print(board)
        return
    for col in range(n):
        if is_safe(board, row, col, n):
            solve_n_queens(n, board + [col], row + 1)

solve_n_queens(4)

---

5. 시간 및 공간 복잡도

문제 유형	시간 복잡도
N-Queen	O(n!)
순열 생성	O(n!)
조합	O(2^n)

• 공간 복잡도: O(n) (재귀 깊이, 보드/방문 배열 등)
• 백트래킹은 완전 탐색이므로 지수 시간 복잡도가 일반적이다.

---

6. 특징 및 장단점

항목	장점	단점
탐색 성능	가지치기를 통해 일부 경우 제외 가능	최악의 경우 모든 경로 탐색
구현 난이도	구조가 단순하며 재귀 기반	상태 저장 및 복원이 필요함
적합 문제	조합, 경로 탐색, 제약 조건 있는 문제	대용량 입력에는 비효율적

---

7. 시각적 예시 (4-Queen 예시)

1. 첫 번째 행: 모든 열 시도
2. 두 번째 행: 첫 번째 퀸과 충돌하지 않는 열 선택
3. 조건 위배 시 → 이전 행으로 백트래킹
4. 최종적으로 가능한 경우만 출력

---

8. 백트래킹 vs 완전 탐색 vs DFS

항목	백트래킹	완전 탐색	DFS
조건 가지치기	O	X	일부 O (그래프 기반)
상태 복귀	O	O	O
대표 문제	N-Queen, Sudoku	모든 조합	미로, 연결 요소

---

9. 활용 분야

분야	활용 예시
퍼즐/게임	N-Queen, Sudoku, 미로 문제
수학	조합론, 순열, 부분집합, 조합합
보안	암호 키 탐색, 해시 충돌 탐색
최적화 문제	제약 조건 기반 스케줄링, 구성 탐색

---

10. 결론

백트래킹은 가능한 모든 경우를 탐색하되, 필요 없는 경우는 조기에 포기함으로써 효율적으로 문제를 해결하는 탐색 전략이다. 순열, 조합, 경로, 퍼즐 등 다양한 탐색 문제에서 강력하며, DFS 기반 구조와 재귀 호출을 통해 구현도 직관적이다. 알고리즘 문제풀이의 핵심 기법 중 하나로 반드시 숙지해야 할 알고리즘이다.