[Algorithm] 백트래킹(Backtracking)

백트래킹이란?

백트래킹(Backtracking)은 문제 해결 과정에서 가능한 모든 해를 탐색하되, 현재 경로가 해답이 될 수 없다고 판단되면 더 이상 진행하지 않고 이전 단계로 되돌아가는 알고리즘 기법이다.

완전탐색 알고리즘인 DFS와 차이점은 DFS는 가능한 모든 경로(후보)를 탐색한다. 따라서, 불필요한 경로를 사전에 차단하는 행동이 없다.

백트래킹의 작동 원리

1. 후보 해 탐색: 가능한 해의 후보를 트리 구조로 표현하고, 루트부터 시작하여 각 노드를 탐색한다.
2. 유망성 검사: 각 노드에서 현재까지의 선택이 해답이 될 수 있는지 판단단한다. 조건을 만족하지 않으면 해당 노드를 더 이상 탐색하지 않고 이전 단계로 돌아간다.
3. 재귀적 탐색: 유망한 노드에 대해서는 재귀적으로 탐색을 진행하여 모든 가능한 해를 찾는다.

백트래킹의 특징

1. 완전 탐색: 모든 가능한 해를 탐색하지만, 유망하지 않은 경로는 조기에 포기하여 효율성을 높인다.
2. 가지치기(Pruning): 조건을 만족하지 않는 경로를 미리 제거함으로써 탐색 공간을 축소한다.

백트래킹 핵심 코드 (python)

def back(num,cnt):
    if num>len(target_list):
        return
    
    if cnt== R:
        for idx in arr:
        	# 메인 로직 수행
        return

    arr.append(num)
    back(num+1,cnt+1)
    arr.pop()
    back(num+1,cnt)
    

결론

백트래킹의 과정은 각 단계에서 선택하거나 선택하지 않음을 반복하면서 가능한 모든 경우의 수를 탐색하는 조합에도 사용할 수 있다. 기저 조건에 도달했을 때 유효한 선택을 저장하고, 그 외의 경우는 더 이상 탐색하지 않도록 되돌아가서 다른 경로를 시도해야 한다.