개념
모든 경우의 수를 탐색하되, 조건을 만족하지 않으면 되돌아가는 알고리즘
DFS + **가지치기(Pruning)**로 불필요한 탐색 제거
특징
백트래킹 vs 브루트포스
| 특성 | 브루트포스 | 백트래킹 |
|---|---|---|
| 탐색 | 모든 경우 탐색 | 조건 불만족 시 중단 |
| 효율 | 비효율적 | 상대적으로 효율적 |
| 구현 | 간단 | 조건 판단 필요 |
장점
- 모든 경우를 확인하면서도 가지치기로 시간 단축
- 해가 존재하는지 확인 가능
- 제약 조건이 있는 문제에 효과적
단점
- 최악의 경우 모든 경우를 탐색 (지수 시간)
- 조건 설정이 중요
백트래킹 템플릿
def backtrack(path, candidates):
# 1. 목표 달성 (Base Case)
if is_goal(path):
result.append(path[:])
return
# 2. 가지치기 (Pruning)
if not is_valid(path):
return
# 3. 후보 탐색
for candidate in candidates:
# 선택
path.append(candidate)
# 재귀 호출
backtrack(path, next_candidates)
# 선택 취소 (백트래킹)
path.pop()기본 예제
1. N-Queen 문제
문제: N×N 체스판에 N개의 퀸을 서로 공격하지 않게 배치
def solve_n_queens(n):
result = []
def is_valid(board, row, col):
# 같은 열 체크
for i in range(row):
if board[i] == col:
return False
# 왼쪽 대각선 체크
for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
if board[i] == j:
return False
# 오른쪽 대각선 체크
for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
if board[i] == j:
return False
return True
def backtrack(row, board):
# 모든 행에 퀸 배치 완료
if row == n:
result.append(board[:])
return
# 각 열에 퀸 배치 시도
for col in range(n):
if is_valid(board, row, col):
board[row] = col
backtrack(row + 1, board)
board[row] = -1 # 백트래킹
backtrack(0, [-1] * n)
return result
# 테스트
solutions = solve_n_queens(4)
print(f"4-Queen 해의 개수: {len(solutions)}") # 2
# 시간복잡도: O(n!)
# 공간복잡도: O(n)핵심: 각 행에 하나씩 배치하며, 유효성 검사로 가지치기
2. 스도쿠 해결
문제: 9×9 스도쿠 퍼즐 풀기
def solve_sudoku(board):
def is_valid(board, row, col, num):
# 행 체크
if num in board[row]:
return False
# 열 체크
if num in [board[i][col] for i in range(9)]:
return False
# 3×3 박스 체크
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for i in range(box_row, box_row + 3):
for j in range(box_col, box_col + 3):
if board[i][j] == num:
return False
return True
def backtrack():
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if backtrack():
return True
board[i][j] = 0 # 백트래킹
return False
return True
backtrack()
return board
# 테스트
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]
]
solve_sudoku(board)핵심: 빈 칸마다 1-9를 시도하며, 규칙 위반 시 백트래킹
자주 나오는 문제 유형
1. 조합의 합 (Combination Sum)
문제: 합이 target이 되는 숫자 조합 찾기 (중복 선택 가능)
def combination_sum(candidates, target):
result = []
def backtrack(start, path, total):
# 목표 달성
if total == target:
result.append(path[:])
return
# 가지치기
if total > target:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
# 같은 숫자 재사용 가능하므로 start=i
backtrack(i, path, total + candidates[i])
path.pop()
backtrack(0, [], 0)
return result
# 테스트
print(combination_sum([2, 3, 6, 7], 7))
# [[2, 2, 3], [7]]
# 시간복잡도: O(n^(target/min))핵심: 같은 원소 재사용 가능, 합이 target 초과 시 가지치기
2. 단어 검색 (Word Search)
문제: 2D 보드에서 단어를 찾을 수 있는지 확인
def word_search(board, word):
rows, cols = len(board), len(board[0])
def backtrack(r, c, index):
# 단어를 모두 찾음
if index == len(word):
return True
# 범위 체크 및 문자 일치 확인
if (r < 0 or r >= rows or c < 0 or c >= cols or
board[r][c] != word[index]):
return False
# 방문 표시
temp = board[r][c]
board[r][c] = '#'
# 4방향 탐색
found = (backtrack(r + 1, c, index + 1) or
backtrack(r - 1, c, index + 1) or
backtrack(r, c + 1, index + 1) or
backtrack(r, c - 1, index + 1))
# 백트래킹 (방문 표시 복원)
board[r][c] = temp
return found
# 모든 위치에서 시작
for i in range(rows):
for j in range(cols):
if backtrack(i, j, 0):
return True
return False
# 테스트
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
print(word_search(board, "ABCCED")) # True
print(word_search(board, "SEE")) # True
print(word_search(board, "ABCB")) # False
# 시간복잡도: O(m*n*4^L) - L: 단어 길이핵심: 방문 표시와 복원으로 중복 방문 방지
3. 괄호 생성
문제: N쌍의 괄호로 만들 수 있는 모든 유효한 조합
def generate_parentheses(n):
result = []
def backtrack(path, open_count, close_count):
# 완성
if len(path) == 2 * n:
result.append(''.join(path))
return
# 여는 괄호 추가
if open_count < n:
path.append('(')
backtrack(path, open_count + 1, close_count)
path.pop()
# 닫는 괄호 추가 (여는 괄호보다 적을 때만)
if close_count < open_count:
path.append(')')
backtrack(path, open_count, close_count + 1)
path.pop()
backtrack([], 0, 0)
return result
# 테스트
print(generate_parentheses(3))
# ["((()))", "(()())", "(())()", "()(())", "()()()"]
# 시간복잡도: O(4^n / √n) - Catalan Number핵심: 여는 괄호 개수가 N 이하, 닫는 괄호는 여는 괄호보다 적게
4. 부분집합 합 문제
문제: 합이 target인 부분집합이 존재하는지 확인
def subset_sum(nums, target):
def backtrack(index, current_sum):
# 목표 달성
if current_sum == target:
return True
# 가지치기
if index >= len(nums) or current_sum > target:
return False
# 현재 원소 포함
if backtrack(index + 1, current_sum + nums[index]):
return True
# 현재 원소 미포함
if backtrack(index + 1, current_sum):
return True
return False
return backtrack(0, 0)
# 테스트
print(subset_sum([3, 34, 4, 12, 5, 2], 9)) # True (4 + 5)
print(subset_sum([3, 34, 4, 12, 5, 2], 30)) # False
# 시간복잡도: O(2^n)핵심: 각 원소를 포함/미포함하는 두 가지 선택
5. 분할된 회문 (Palindrome Partitioning)
문제: 문자열을 모든 부분이 회문이 되도록 분할
def partition(s):
result = []
def is_palindrome(string):
return string == string[::-1]
def backtrack(start, path):
# 문자열 끝까지 도달
if start == len(s):
result.append(path[:])
return
# 가능한 모든 분할 지점 시도
for end in range(start + 1, len(s) + 1):
substring = s[start:end]
# 회문인 경우만 진행
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop()
backtrack(0, [])
return result
# 테스트
print(partition("aab"))
# [["a", "a", "b"], ["aa", "b"]]
print(partition("aabb"))
# [["a","a","b","b"], ["a","a","bb"], ["aa","b","b"], ["aa","bb"]]
# 시간복잡도: O(n * 2^n)핵심: 회문인 경우만 재귀 호출하여 가지치기
6. 전화번호 문자 조합
문제: 전화번호 숫자를 문자로 변환한 모든 조합
def letter_combinations(digits):
if not digits:
return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
# 모든 숫자 처리 완료
if index == len(digits):
result.append(''.join(path))
return
# 현재 숫자에 해당하는 문자들 시도
for letter in phone[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return result
# 테스트
print(letter_combinations("23"))
# ["ad","ae","af","bd","be","bf","cd","ce","cf"]
# 시간복잡도: O(4^n) - 최악의 경우 (7, 9는 4글자)핵심: 각 숫자마다 가능한 문자를 순차적으로 선택
추천 연습 문제
기초
중급
고급
핵심 요약
| 개념 | 설명 |
|---|---|
| 기본 원리 | DFS + 조건 검사 + 되돌아가기 |
| 가지치기 | 조건 불만족 시 탐색 중단 |
| 시간복잡도 | 주로 지수 시간 (O(2^n), O(n!)) |
| 활용 | 순열, 조합, 제약 만족 문제 |
백트래킹 작성 팁
1. 상태 관리
# 상태를 명확히 관리
def backtrack(index, path, used):
# used: 사용 여부 추적
# path: 현재까지 선택한 요소
# index: 현재 위치2. 가지치기 조건
# 조기 종료 조건 명확히
if current_sum > target: # 더 이상 진행 불필요
return
if remaining_count < needed: # 목표 달성 불가
return3. 중복 제거
# 정렬 + 이전 값과 비교
candidates.sort()
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]:
continue # 중복 건너뛰기
backtrack(i + 1, ...)4. 방문 표시
# 2D 배열에서 방문 관리
visited = [[False] * cols for _ in range(rows)]
def backtrack(r, c):
visited[r][c] = True
# 탐색...
visited[r][c] = False # 백트래킹최적화 기법
1. 비트마스킹
# used 배열 대신 비트마스크 사용
def backtrack(used_mask):
for i in range(n):
if not (used_mask & (1 << i)):
backtrack(used_mask | (1 << i))2. 메모이제이션
# 중복 상태 저장
def backtrack(state, memo):
if state in memo:
return memo[state]
# 계산...
memo[state] = result
return result3. 조기 종료
# 하나만 찾으면 되는 경우
def backtrack():
if found_solution:
return True
# 탐색...백트래킹 vs DFS
| 특성 | 백트래킹 | DFS |
|---|---|---|
| 목적 | 해 찾기 | 전체 탐색 |
| 가지치기 | 있음 | 없음 |
| 효율 | 상대적으로 효율적 | 모든 노드 방문 |
| 사용 | 제약 조건 문제 | 그래프 순회 |