백트래킹 안내서 · 1/6
백트래킹(backtracking)은 답을 한 번에 만들지 않고 한 칸씩 채워 가다가, 지금까지 고른 것이 조건을 어기면 바로 앞 단계로 돌아가 다른 선택을 시도하는 탐색 기법입니다. 모든 경우를 끝까지 만들어 본 뒤 검사하는 완전 탐색과 달리, 가망이 없는 길은 중간에 잘라 내므로 같은 문제를 훨씬 적은 시도로 풀 수 있습니다. 이 장에서는 백트래킹을 설명할 때 쓰는 용어와 기본 틀, 그리고 언제 백트래킹을 고르는지 정리합니다.
백트래킹이 탐색하는 공간은 상태 공간 트리(state-space tree)로 그리면 이해하기 쉽습니다. 루트는 아무것도 고르지 않은 빈 상태이고, 한 단계 내려갈 때마다 선택을 하나씩 더합니다. 리프에 도착하면 완성된 후보 하나가 만들어집니다. 예를 들어 [1, 2, 3]의 순열을 만드는 트리는 다음과 같습니다.
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] ... [3,2,1]백트래킹은 이 트리를 깊이 우선 탐색(DFS)으로 내려가되, 어떤 노드가 더 내려가 봐야 해가 될 수 없다고 판단되면 그 아래 가지 전체를 건너뜁니다. 이것을 가지치기(pruning)라고 합니다.
path 같은 리스트로 들고 다닙니다.거의 모든 백트래킹 코드는 세 동작의 반복입니다. 후보를 하나 선택(choose)해 부분해에 넣고, 그 상태에서 재귀로 탐색(explore)한 뒤, 돌아와서 넣었던 것을 되돌립니다(unchoose). 되돌리기가 있어야 하나의 path 리스트를 모든 가지가 함께 쓸 수 있습니다.
def backtrack(path, choices, result):
if is_solution(path):
result.append(path[:]) # 복사해서 저장
return
for c in candidates(path, choices):
if not is_valid(path, c): # 가지치기
continue
path.append(c) # 선택
backtrack(path, choices, result) # 탐색
path.pop() # 되돌리기result.append(path[:])에서 복사를 빼먹으면, 나중에 path가 비워질 때 저장해 둔 결과도 같이 바뀌어 빈 리스트만 남습니다. 백트래킹에서 가장 흔한 실수 가운데 하나입니다.
각 원소를 넣을지 말지 두 갈래로 나누면 부분집합 트리가 됩니다. 원소가 n개면 리프가 2^n개입니다.
def subsets(nums):
result, path = [], []
def dfs(i):
if i == len(nums):
result.append(path[:])
return
path.append(nums[i]) # nums[i]를 넣는 가지
dfs(i + 1)
path.pop()
dfs(i + 1) # 넣지 않는 가지
dfs(0)
return result
print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]길이 n의 0/1 문자열 가운데 1이 연속으로 붙지 않는 것만 만들어 봅니다. 마지막 글자가 1이면 다음에 1을 고르지 않는 것이 가지치기입니다. 잘못된 문자열을 다 만든 뒤 걸러 내는 것보다 훨씬 적게 탐색합니다.
def no_adjacent_ones(n):
out = []
def dfs(s):
if len(s) == n:
out.append(s)
return
dfs(s + "0")
if not s.endswith("1"): # 1 다음 1은 시도하지 않음
dfs(s + "1")
dfs("")
return out
print(no_adjacent_ones(3)) # ['000', '001', '010', '100', '101']n이 20 안팎 이하) 지수 시간이라도 감당할 수 있을 때.반대로 개수만 세면 되고 같은 하위 문제가 반복된다면 DP가, 매 단계의 최선 선택이 전체 최적을 보장한다면 그리디가 더 알맞습니다. 이 비교는 복잡도 장에서 자세히 다룹니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.