[Algorithm] 백트래킹(Backtracking)

백트래킹(Backtracking) 이란?

비선형 구조의 자료를 탐색할 때 깊이 우선 탐색(DFS) 방식으로 경로를 따라가다가, 조건을 확인하였을 때 그 경로가 해결책으로 이어질 것 같지 않다면 더이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄이는 방식이다. 이를 가지치기(Prunning) 라고 한다.

깊이 우선 탐색(DFS) 방식과 유사하지만 DFS는 가능한 모든 경로를 추적하는데 비해서 백트래킹은 가지치키를 통해 불필요한 경로를 차단한다.

일반적으로는 경우의 수가 줄어들지만 최악의 경우에는 여전히 많은 탐색을 요하므로 처리가 불가능하다.

절차

• 트리의 깊이 우선 탐색을 실시한다.
• 조건을 확인하여 각 노드가 유망한지(Promising) 점검한다.
• 노드가 유망하지 않다면, 그 노드의 부모 노드로 돌아가서(Backtrack) 검색을 계속한다.

예를들어, 트리를 탐색하면서 합이 10이되는 경로를 탐색한다고 했을 때, 1번노드에서 출발한 다음 2번노드, 그다음 7번노드, 그다음 10번 노드를 탐색하게 될텐데, 10번노드를 탐색했을때, 이미 합이 1+10=11이므로 10번의 하위 노드를 탐색할 필요가 없어지게 된다.

예제

다음은 백트래킹을 이용하여 1~10의 정수로 이루어진 집합의 부분집합 중, 합계가 10인 부분집합을 구하는 예제이다.

def process_solution(k, result):
    if result != 10:        # 합계가 10이 아니라면 바로 리턴
        return

    arr_subset = []
    for i in range(1, k+1):
        if arr[i] == 1:     # 만약 부분집합이 해당 원소를 포함한다면
            arr_subset.append(data[i])
    print(arr_subset)       # 부분집합 출력


def subset(k, n, result):   # 부분집합 구하는 함수
    global cnt

    if result > 10:         # 만약 합계가 10 이상이라면 리턴 -> 가지치기(Prunning)
        return

    if k == n:              # 1~n 까지 모든 원소에 대해 탐색을 마쳤다면 조건을 만족하는지 확인
        process_solution(k, result)
    else:
        k += 1
        arr[k] = 1          # k 포함하여 부분집합 계산
        subset(k, n, result + data[k])
        arr[k] = 0          # k 포함하지 않고 부분집합 계산
        subset(k, n, result)
    cnt += 1 

cnt = 0
NMAX = 10
data = [0] + list(range(1, NMAX + 1))
arr = [0 for _ in range(NMAX + 1)]
subset(0, NMAX, 0)
print(cnt)