# [06-05] 백트래킹 (Backtracking)
백트래킹은 모든 가능한 경우를 탐색하되, 불가능한 경로는 조기에 포기하여 효율적으로 해를 찾는 알고리즘 설계 기법입니다.
🎯 백트래킹 (Backtracking) 이란 무엇인가
백트래킹의 기본 개념
백트래킹은 해를 찾아가다가 막히면 되돌아가서 다른 길을 시도하는 방법입니다.
실생활 비유:
미로 탈출:
1. 한 길을 선택해서 간다
2. 막다른 길이면? → 되돌아간다 (Backtrack)
3. 다른 길을 선택한다
4. 출구를 찾을 때까지 반복
입구
|
┌───┴───┐
A B
| |
막힘 ┌──┴──┐
C D
| |
출구 막힘
경로: 입구 → A (막힘!) → 입구 (되돌아감) → B → C (출구 발견!)또 다른 예시:
- 옷 입기: 조합이 이상하면 다시 벗고 다른 옷 선택
- 퍼즐: 맞지 않으면 조각을 빼고 다른 곳 시도
- 의사결정: 잘못된 선택이면 되돌아가서 재선택
백트래킹 vs 완전 탐색
백트래킹과 완전 탐색(Brute Force)의 차이를 이해하는 것이 중요합니다.
완전 탐색: 모든 경우를 끝까지 확인
예: 배열 [10, 5, 3, 2]에서 합이 15인 부분집합 찾기
모든 부분집합 (2^4 = 16가지):
[], [10], [5], [3], [2],
[10,5], [10,3], [10,2], [5,3], [5,2], [3,2],
[10,5,3], [10,5,2], [10,3,2], [5,3,2],
[10,5,3,2]
→ 16가지 모두 확인해야 답을 찾음백트래킹: 불가능하다고 판단되면 즉시 포기
같은 문제를 백트래킹으로:
[10] = 10 (15 미만, 계속 가능)
[10,5] = 15 ✓ 찾음! 끝
→ 단 2번 만에 찾음!
나머지는 확인할 필요 없음핵심 차이:
완전 탐색:
- 장점: 단순, 모든 해를 반드시 찾음
- 단점: 매우 느림 (불필요한 탐색 많음)
백트래킹:
- 장점: 불가능한 경로 조기 포기 → 빠름
- 단점: 가지치기 조건을 찾아야 함백트래킹의 핵심 요소
백트래킹은 항상 다음 세 단계를 반복합니다:
1. 선택 (Choose)
현재 상태에서 가능한 선택을 한다.
for choice in available_choices:
make_choice(choice)2. 탐색 (Explore)
선택한 경로를 재귀적으로 탐색한다.
backtrack(new_state)3. 되돌리기 (Unchoose)
선택을 취소하고 이전 상태로 되돌린다.
undo_choice(choice)백트래킹 템플릿:
def backtrack(state):
# 기저 조건: 해를 찾았거나 불가능
if is_solution(state):
add_to_result(state)
return
# 가지치기: 더 이상 진행 불가능
if is_invalid(state):
return
# 모든 선택지 시도
for choice in get_choices(state):
make_choice(choice) # 1. 선택
backtrack(new_state) # 2. 탐색
undo_choice(choice) # 3. 되돌리기이제 이 템플릿을 구체적인 문제에 적용해봅시다.
🔢 순열 생성
순열이란 무엇인가
백트래킹을 이해하기 위해 먼저 간단한 문제부터 시작합니다. 순열(Permutation)은 주어진 원소들을 순서를 고려하여 나열하는 모든 경우입니다.
왜 순열 문제로 시작하나?
순열은 백트래킹의 "선택-탐색-되돌리기" 패턴을 명확하게 보여주는 가장 단순한 예제입니다. 복잡한 제약 조건 없이 백트래킹의 작동 원리를 이해할 수 있습니다.
순열의 예:
[1, 2, 3]의 모든 순열:
[1, 2, 3] - 1을 먼저, 2를 두 번째, 3을 마지막
[1, 3, 2] - 1을 먼저, 3을 두 번째, 2를 마지막
[2, 1, 3] - 2를 먼저, 1을 두 번째, 3을 마지막
[2, 3, 1] - 2를 먼저, 3을 두 번째, 1을 마지막
[3, 1, 2] - 3을 먼저, 1을 두 번째, 2를 마지막
[3, 2, 1] - 3을 먼저, 2를 두 번째, 1을 마지막
총 3! = 6가지순서가 중요합니다:
- [1, 2, 3]과 [1, 3, 2]는 다른 순열입니다
- 같은 원소를 사용했지만 순서가 다르면 다른 것
백트래킹으로 순열 만들기
순열을 만드는 과정을 백트래킹으로 생각해 봅시다.
핵심 아이디어:
1. 첫 번째 위치에 무엇을 놓을까?
→ 1, 2, 3 중 하나를 선택
2. 첫 번째에 1을 선택했다면, 두 번째는?
→ 남은 2, 3 중 하나를 선택
3. 첫 번째에 1, 두 번째에 2를 선택했다면, 세 번째는?
→ 남은 3만 선택 가능 → [1, 2, 3] 완성!
4. 다시 되돌아가서 두 번째를 3으로 선택
→ [1, 3, 2] 완성!
5. 계속 반복...선택 트리로 시각화:
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2][1,3] [2,1][2,3] [3,1][3,2]
| | | | | |
[1,2,3][1,3,2] [2,1,3][2,3,1] [3,1,2][3,2,1]
각 경로가 하나의 순열!이제 이것을 코드로 구현해 봅시다.
문제 설명
입력: [1, 2, 3]
출력: 모든 순열
[[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]]구현
def permute(nums):
"""
모든 순열 생성 - 백트래킹
nums: 숫자 배열
Returns: 모든 순열의 리스트
"""
result = []
def backtrack(current, remaining):
"""
백트래킹 재귀 함수
current: 현재까지 만든 순열 * 예: [1, 2] - 첫 번째에 1, 두 번째에 2
remaining: 아직 사용하지 않은 숫자들 * 예: [3] - 아직 3만 남음
동작 원리:
1. 남은 숫자가 없으면 → 순열 완성!
2. 남은 숫자 각각을 선택해서 시도
3. 선택 → 재귀 → 되돌리기
"""
# ===== 기저 조건 =====
# 모든 숫자를 사용했으면 (남은 게 없으면)
if not remaining:
result.append(current[:]) # 완성된 순열을 결과에 추가, current[:]로 복사본 저장 (중요!)
return
# ===== 재귀 =====
# 남은 숫자 각각을 다음 위치에 놓아보기
for i in range(len(remaining)):
# 1. 선택: i번째 숫자를 선택
chosen = remaining[i]
new_current = current + [chosen] # 새로운 상태 만들기, current에 chosen 추가
new_remaining = remaining[:i] + remaining[i+1:] # remaining에서 chosen 제거(i번째 숫자가 빠짐) -> 새로운 리스트 생성
# 2. 탐색: 다음 단계로 재귀
backtrack(new_current, new_remaining)
# 3. 되돌리기: (여기서는 불필요 - 새 리스트를 만들었으므로)
# 원래 current와 remaining은 변하지 않음
backtrack([], nums) # 초기 호출: 빈 순열로 시작, 모든 숫자가 남아 있음
return result
# 사용 예시
nums = [1, 2, 3]
perms = permute(nums)
print(f"순열 개수: {len(perms)}")
for p in perms:
print(p)
# 출력:
# 순열 개수: 6
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]실행 과정 상세 추적:
backtrack([], [1,2,3]) 호출
├─ i=0: 1을 선택
│ backtrack([1], [2,3])
│
│ ├─ i=0: 2를 선택
│ │ backtrack([1,2], [3])
│ │
│ │ └─ i=0: 3을 선택
│ │ backtrack([1,2,3], [])
│ │ → 남은 것 없음! [1,2,3] 완성 ✓
│ │
│ └─ i=1: 3을 선택
│ backtrack([1,3], [2])
│
│ └─ i=0: 2를 선택
│ backtrack([1,3,2], [])
│ → 남은 것 없음! [1,3,2] 완성 ✓
│
├─ i=1: 2를 선택
│ backtrack([2], [1,3])
│ └─ ... (계속)
│
└─ i=2: 3을 선택
backtrack([3], [1,2])
└─ ... (계속)
이렇게 모든 가능한 조합을 탐색!이 예제를 통해 백트래킹의 핵심 패턴을 익혔습니다. 이제 더 복잡한 제약 조건이 있는 문제로 넘어갑시다.
♕ N-Queen 문제
N-Queen이란 무엇인가
이제 백트래킹의 진가를 발휘하는 문제를 봅시다. N-Queen 문제는 백트래킹의 고전적인 예제로, "가지치기"의 중요성을 명확하게 보여줍니다.
문제 소개:
N×N 체스판에 N개의 퀸(Queen)을 배치하되, 서로 공격할 수 없게 놓아야 합니다.
왜 이 문제가 백트래킹에 적합한가?
- 거대한 탐색 공간: 64개 칸에서 8개를 선택하는 경우의 수는 천문학적
- 명확한 제약 조건: 퀸들이 서로 공격하면 안 됨
- 조기 판단 가능: 퀸을 놓는 순간 불가능 여부를 알 수 있음
이런 특성 때문에 백트래킹이 완벽하게 적용됩니다.
퀸의 이동 규칙 이해하기
체스를 모르는 분들을 위한 설명:
퀸(Queen)은 체스에서 가장 강력한 말로, 다음 방향으로 무제한 이동할 수 있습니다:
퀸의 공격 방향: 가로 (→, ←), 세로 (↑, ↓), 대각선 (↗, ↘, ↙, ↖)
0 1 2 3
┌───┬───┬───┬───┐
0 │ X │ X │ X │ X │
├───┼───┼───┼───┤
1 │ X │ X │ Q │ X │ ← (1,2)에 퀸
├───┼───┼───┼───┤
2 │ │ X │ X │ X │
├───┼───┼───┼───┤
3 │ X │ │ X │ │
└───┴───┴───┴───┘
X 표시된 모든 곳을 공격 가능 → 다른 퀸을 놓을 수 없음!문제를 단순화하기
완전 탐색으로 접근하면:
- 64개 칸에서 8개를 선택: C(64, 8) = 약 44억 가지!
핵심 통찰: 각 행에 정확히 1개씩만!
왜냐하면:
- 같은 행에 2개 이상 → 가로 공격으로 불가능
- N개 퀸을 N개 행에 → 각 행에 정확히 1개
이렇게 하면:
- 각 행마다 어느 열에 놓을지만 결정
- 8 × 8 × 8 × 8 × 8 × 8 × 8 × 8 = 약 1,600만 가지
- 여전히 많지만 44억보다는 훨씬 적음!
백트래킹으로 더 줄일 수 있음!문제 설명
4×4 체스판에 4개의 퀸 배치:
해답 예시:
0 1 2 3
┌───┬───┬───┬───┐
0 │ │ Q │ │ │ ← 0행 1열
├───┼───┼───┼───┤
1 │ │ │ │ Q │ ← 1행 3열
├───┼───┼───┼───┤
2 │ Q │ │ │ │ ← 2행 0열
├───┼───┼───┼───┤
3 │ │ │ Q │ │ ← 3행 2열
└───┴───┴───┴───┘
표현: [1, 3, 0, 2]
의미: board[i] = j → i행의 퀸이 j열에 있음백트래킹 전략
접근 방법:
1. 0행부터 시작
2. 0행의 각 열(0, 1, 2, 3)을 시도
- 안전하면 퀸 배치
- 1행으로 재귀
- 1행에서 실패하면 0행으로 되돌아와서 다음 열 시도
3. N행까지 모두 배치하면 해 발견!가지치기 조건:
현재 위치 (row, col)에 퀸을 놓을 수 없는 경우:
1. 같은 열에 이미 퀸이 있음 * 예: (0,1)에 이미 퀸 → (3,1)에 놓을 수 없음
2. 왼쪽 대각선(\)에 퀸이 있음 * 예: (0,0)에 퀸 → (1,1), (2,2), (3,3)에 놓을 수 없음
3. 오른쪽 대각선(/)에 퀸이 있음 * 예: (0,3)에 퀸 → (1,2), (2,1), (3,0)에 놓을 수 없음
→ 이런 경우는 시도조차 하지 않음!구현
def solve_n_queens(n):
"""
N-Queen 문제 - 백트래킹
n: 체스판 크기 (n×n)
Returns: 모든 가능한 해의 리스트
각 해는 [col0, col1, ..., coln-1] 형태 (i행의 퀸이 col i열에 있음)
"""
result = []
# board[i] = j: i번 행의 퀸이 j번 열에 있음
# -1은 아직 퀸을 안 놓음
board = [-1] * n
def is_safe(row, col):
"""
(row, col) 위치에 퀸을 놓을 수 있는가?
확인 사항:
1. 같은 열에 다른 퀸이 있는가?
2. 왼쪽 대각선(\)에 다른 퀸이 있는가?
3. 오른쪽 대각선(/)에 다른 퀸이 있는가?
# 같은 행은 확인 불필요 - 각 행에 1개씩만 놓으므로)
row: 퀸을 놓을 행
col: 퀸을 놓을 열
Returns: bool: 안전하면 True
"""
# 이전 행들(0 ~ row-1)만 확인하면 됨. row 이후 행에는 아직 퀸을 놓지 않았음.
for prev_row in range(row):
prev_col = board[prev_row]
# 1. 같은 열에 퀸이 있는가? * 예: board[0]=1이면 (0,1)에 퀸, (3,1)에 놓으려 하면 같은 열이므로 불가능
if prev_col == col:
return False
# 2. 대각선에 있는가? * 대각선 판단 원리: 행 차이와 열 차이(절대값)가 같으면 같은 대각선
# 예1: (0,0)과 (1,1): 행 차이: 1-0 = 1, 열 차이: 1-0 = 1 → 1 == 1, 같은 대각선! (\방향)
# 예2: (0,3)과 (1,2): 행 차이: 1-0 = 1, 열 차이: |2-3| = 1 → 1 == 1, 같은 대각선! (/방향)
# 예3: (0,0)과 (2,3): 행 차이: 2-0 = 2, 열 차이: |3-0| = 3 → 2 != 3, 다른 대각선 (안전)
row_diff = row - prev_row # row는 prev_row보다 항상 큼
col_diff = abs(col - prev_col)
if row_diff == col_diff:
return False # 대각선에 있음!
# 모든 확인 통과 → 안전
return True
def backtrack(row):
"""
row번 행에 퀸 배치
row: 현재 행 번호
동작:
1. 모든 행에 퀸을 놓았으면 → 해 발견!
2. 현재 행의 각 열을 시도
- 안전한 위치면 퀸 배치
- 다음 행으로 재귀
- 실패하면 퀸 제거하고 다음 열 시도
"""
# ===== 기저 조건 =====
# 모든 행에 퀸을 배치했으면
if row == n: # 해를 찾았다!
result.append(board[:]) # 복사본 저장
return
# ===== 재귀 =====
# 현재 행의 각 열을 시도
for col in range(n):
if not is_safe(row, col): # 가지치기: 이 위치가 안전한지 확인
continue # 안전하지 않으면 건너뛰기
# 1. 선택: 퀸 배치
board[row] = col
# 2. 탐색: 다음 행으로
backtrack(row + 1)
# 3. 되돌리기: 퀸 제거 (다음 열을 시도하기 위해)
board[row] = -1
backtrack(0) # 0행부터 시작
return result
# 사용 예시
n = 4
solutions = solve_n_queens(n)
print(f"{n}×{n} 체스판의 해: {len(solutions)}개\n")
for i, solution in enumerate(solutions, 1):
print(f"해 {i}: {solution}")
# 체스판 시각화
for row in range(n):
line = ""
for col in range(n):
if solution[row] == col:
line += "Q "
else:
line += ". "
print(line)
print()
# 출력:
# 4×4 체스판의 해: 2개
# 해 1: [1, 3, 0, 2]
# . Q . .
# . . . Q
# Q . . .
# . . Q .
# 해 2: [2, 0, 3, 1]
# . . Q .
# Q . . .
# . . . Q
# . Q . .실행 과정 추적 (4-Queen):
backtrack(0) - 0행에 퀸 배치 시도
├─ col=0: is_safe(0, 0) → True (첫 퀸이므로 안전)
│ board = [0, -1, -1, -1] ← 0행 0열에 퀸
│
│ backtrack(1) - 1행 시도
│ ├─ col=0: is_safe(1, 0) → False (같은 열!)
│ ├─ col=1: is_safe(1, 1) → False (대각선!)
│ ├─ col=2: is_safe(1, 2) → True
│ │ board = [0, 2, -1, -1]
│ │
│ │ backtrack(2) - 2행 시도
│ │ ├─ col=0: is_safe(2, 0) → False (대각선!)
│ │ ├─ col=1: is_safe(2, 1) → False (대각선!)
│ │ ├─ col=2: is_safe(2, 2) → False (같은 열!)
│ │ └─ col=3: is_safe(2, 3) → False (대각선!)
│ │ → 모두 실패! 되돌아감
│ │
│ └─ col=3: is_safe(1, 3) → True
│ board = [0, 3, -1, -1]
│ backtrack(2) - 2행 시도
│ └─ ... (계속)
│
├─ col=1: is_safe(0, 1) → True
│ board = [1, -1, -1, -1]
│ backtrack(1)
│ └─ ... (계속, 해 발견!)
│
└─ ... (계속)
백트래킹 덕분에 불가능한 경로는 즉시 포기!N-Queen 문제를 통해 백트래킹이 어떻게 거대한 탐색 공간을 효율적으로 탐색하는지 보았습니다. 이제 또 다른 유명한 퍼즐 문제를 봅시다.
🧩 스도쿠 풀이
스도쿠란 무엇인가
스도쿠(Sudoku)는 일본에서 유래한 세계적으로 유명한 숫자 퍼즐입니다. 백트래킹의 실전 응용을 보여주는 완벽한 예제입니다.
왜 스도쿠가 백트래킹 문제인가?
- 제약 조건이 명확: 행/열/박스 규칙
- 빈 칸마다 1~9 시도: 완전 탐색하면 9^빈칸수 (엄청남!)
- 조기 판단 가능: 숫자를 놓는 순간 규칙 위반 여부 확인
- 되돌아가기: 막히면 이전 선택 취소
이런 특성이 백트래킹에 완벽하게 맞습니다.
스도쿠 규칙
9×9 격자를 1~9 숫자로 채우기
규칙:
1. 각 행에 1~9가 정확히 한 번씩
2. 각 열에 1~9가 정확히 한 번씩
3. 각 3×3 박스에 1~9가 정확히 한 번씩
입력 예시 (0은 빈 칸):
0 1 2 3 4 5 6 7 8
0 5 3 0 | 0 7 0 | 0 0 0
1 6 0 0 | 1 9 5 | 0 0 0
2 0 9 8 | 0 0 0 | 0 6 0
------+-------+------
3 8 0 0 | 0 6 0 | 0 0 3
4 4 0 0 | 8 0 3 | 0 0 1
5 7 0 0 | 0 2 0 | 0 0 6
------+-------+------
6 0 6 0 | 0 0 0 | 2 8 0
7 0 0 0 | 4 1 9 | 0 0 5
8 0 0 0 | 0 8 0 | 0 7 9
**3×3 박스란?**
9×9 보드를 9개의 3×3 박스로 나눔:
박스 0 | 박스 1 | 박스 2
------+--------+-------
박스 3 | 박스 4 | 박스 5
------+--------+-------
박스 6 | 박스 7 | 박스 8
각 박스 안에도 1~9가 한 번씩만!백트래킹 전략
접근 방법:
1. 빈 칸(0)을 찾는다
2. 그 칸에 1~9를 시도
- 규칙을 위반하지 않으면 숫자 배치
- 다음 빈 칸으로 재귀
- 성공하면 완료!
- 실패하면 숫자 제거하고 다음 숫자 시도
3. 모든 빈 칸을 채우면 완성!가지치기:
숫자 num을 (row, col)에 놓을 수 없는 경우:
1. 같은 행에 num이 이미 있음
2. 같은 열에 num이 이미 있음
3. 같은 3×3 박스에 num이 이미 있음
→ 이런 경우는 시도하지 않음!문제 설명
입력: 부분적으로 채워진 9×9 스도쿠
출력: 완성된 스도쿠 (불가능하면 False)구현
def solve_sudoku(board):
"""
스도쿠 풀이 - 백트래킹
board: 9×9 리스트 (0은 빈 칸)
Returns: bool: 해결 성공 여부 (board가 직접 수정됨)
"""
def is_valid(board, row, col, num):
"""
(row, col)에 num을 놓을 수 있는가?
확인:
1. 같은 행에 num이 없는가?
2. 같은 열에 num이 없는가?
3. 같은 3×3 박스에 num이 없는가?
board: 스도쿠 보드
row, col: 확인할 위치
num: 놓으려는 숫자 (1~9)
Returns: bool: 놓을 수 있으면 True
"""
# 1. 같은 행 확인: 0~8열을 확인하며 num이 있는지
for c in range(9):
if board[row][c] == num:
return False # 이미 있음!
# 2. 같은 열 확인: 0~8행을 확인하며 num이 있는지
for r in range(9):
if board[r][col] == num:
return False # 이미 있음!
# 3. 같은 3×3 박스 확인
# 박스의 시작 좌표 계산: * 예: (4, 5) → 박스는 (3, 3)부터 시작
# 좌표 계산 방법:
# row=4 → 4//3 = 1 → 1*3 = 3 (박스 행 시작)
# col=5 → 5//3 = 1 → 1*3 = 3 (박스 열 시작)
# 왜 이렇게?
# 0~2 → 0//3=0 → 0*3=0 (첫 번째 박스)
# 3~5 → 3//3=1 → 1*3=3 (두 번째 박스)
# 6~8 → 6//3=2 → 2*3=6 (세 번째 박스)
box_row = (row // 3) * 3
box_col = (col // 3) * 3
# 박스 내 9개 칸 확인
# box_row ~ box_row+2 (3개 행)
# box_col ~ box_col+2 (3개 열)
for r in range(box_row, box_row + 3):
for c in range(box_col, box_col + 3):
if board[r][c] == num:
return False # 이미 있음!
return True # 모든 확인 통과!
def backtrack():
"""
빈 칸을 채워나가는 재귀 함수
Returns: bool: 스도쿠를 완성했으면 True
동작:
1. 빈 칸(0) 찾기
2. 없으면 → 모두 채웠다! 완성!
3. 있으면 → 1~9를 시도
- 유효하면 숫자 배치
- 재귀로 다음 칸
- 성공하면 True 반환
- 실패하면 숫자 제거하고 다음 시도
4. 1~9 모두 실패 → False (되돌아가야 함)
"""
# ===== 빈 칸 찾기 =====
# 9×9 보드를 순회하며 0인 칸 찾기
for row in range(9):
for col in range(9):
if board[row][col] == 0: # 빈 칸 발견!
# ===== 1~9를 시도 =====
for num in range(1, 10):
# 가지치기: 이 숫자가 유효한가?
if is_valid(board, row, col, num):
# 1. 선택: 숫자 배치
board[row][col] = num
# 2. 탐색: 다음 빈 칸으로
if backtrack():
return True # 성공!
# 3. 되돌리기: 숫자 제거 (이 숫자로는 완성 못 함)
board[row][col] = 0
# 1~9 모두 실패 → 이전 선택이 잘못됨
return False
# ===== 빈 칸이 없음 =====
return True # 모든 칸을 채웠다 → 완성!
return backtrack()
# 사용 예시
board = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
print("풀기 전:")
for row in board:
print(row)
if solve_sudoku(board):
print("\n풀이 완료!")
for row in board:
print(row)
else:
print("\n해가 없습니다.")스도쿠 풀이를 통해 백트래킹이 복잡한 제약 조건이 있는 실전 문제를 어떻게 해결하는지 보았습니다.
💡 실무 팁
백트래킹을 사용할 때
-
제약 조건이 명확한 문제
- N-Queen, 스도쿠처럼 규칙이 분명
- 불가능한 선택을 빠르게 판단 가능
-
모든 해를 찾아야 하는 문제
- 순열, 조합, 부분집합
- 최적해가 아닌 가능한 모든 해
-
탐색 공간이 크지만 가지치기가 효과적인 문제
- 완전 탐색은 너무 느림
- 많은 경우를 조기에 제외 가능
가지치기 최적화
# 나쁜 가지치기: 비용이 큼
def is_valid(state):
# 복잡한 계산을 먼저...
return expensive_check(state)
# 좋은 가지치기: 빠른 확인부터
def is_valid(state):
# 간단한 확인부터
if simple_check_failed(state):
return False
# 복잡한 확인은 나중에
return expensive_check(state)재귀 깊이 주의
- Python 기본 재귀 한계: 약 1000
- 필요시 증가:
sys.setrecursionlimit(10000) - 또는 반복문으로 변환 고려
디버깅 팁
def backtrack(state, depth=0):
# 들여쓰기로 재귀 깊이 표시
indent = " " * depth
print(f"{indent}State: {state}")
# ... 백트래킹 로직🎯 핵심 정리
백트래킹의 본질
- 모든 경우를 탐색하되 불가능한 경로는 조기 포기
- 선택 → 탐색 → 되돌리기
- DFS + 가지치기
백트래킹 템플릿
def backtrack(state):
if is_solution(state):
save_solution(state)
return
if is_invalid(state): # 가지치기
return
for choice in get_choices(state):
make_choice(choice)
backtrack(new_state)
undo_choice(choice)주요 문제 유형
문제 특징 시간복잡도
------------------------------------------------------
순열 모든 배열 O(n!)
N-Queen 제약 조건 만족 O(n!) - 가지치기로 감소
스도쿠 퍼즐 풀이 지수 시간 - 가지치기로 감소백트래킹 vs 다른 기법
완전 탐색:
- 모든 경우 끝까지
- 가지치기 없음
- 느림
동적 계획법:
- 중복 부분 문제
- 최적 부분 구조
- 다른 유형의 문제
백트래킹:
- 불가능하면 조기 포기
- 가지치기 있음
- 훨씬 빠름🔗 다음 글에서는
[06-06] 분기 한정 (Branch & Bound)
- 분기 한정의 개념: 백트래킹에 한계값을 추가하여 최적화 문제 해결
- 한계 함수: 현재 경로의 가능성을 미리 계산하여 가지치기
- 0-1 배낭 문제: 분기 한정으로 최적해 빠르게 찾기
- 외판원 문제(TSP): 경로 탐색에서 분기 한정 적용
이전 글: [06-04] 동적 계획법
다음 글: [06-06] 분기 한정
시리즈: P1. Computer Science 기초
AI 전문가를 꿈꾸는 도전자