[자료구조] 백트레킹

• 백트래킹(Backtracking)은 가능한 모든 경우를 탐색하는 알고리즘으로, 트리 형태로 문제를 해결합니다.
• 일반적으로 DFS(깊이 우선 탐색)를 기반으로 하며, 조건을 만족하지 않으면 더 깊이 탐색하지 않고 되돌아오는 방식으로 시간 효율성을 높입니다.

1. 백트래킹의 일반적인 흐름:

1. 트리 구조로 문제 해결:
   • 문제를 가능한 모든 경우의 수로 확장해서 탐색할 수 있는 트리 형태로 생각합니다. 각 노드는 결정할 사항을 나타내며, 각 단계는 배열의 인덱스 또는 선택할 후보를 의미합니다.

2. DFS 탐색:
   • DFS를 이용하여 가능한 모든 경우를 탐색합니다. 이를 위해 재귀 함수를 사용합니다.
   • 탐색할 때마다 현재 상태에서 다음 상태로 이동하며, 이 과정에서 조건을 확인해 불필요한 경로를 배제할 수 있습니다.

3. 종료 조건:
   • 주로 인덱스가 배열의 끝에 도달하거나, 원하는 조건을 만족한 경우 탐색을 종료합니다.

4. 경우 나누기:
   • 주어진 배열이나 집합에서 현재 원소를 사용할 것인지 아닌지를 나눕니다.
   • 사용하는 경우와 사용하지 않는 경우를 나눠서 재귀 호출을 이어갑니다.

2. 백트래킹의 일반적인 구조:

def dfs(n, sm, cnt):
    # 1. 종료 조건
    if n == len(lst):  # 모든 원소를 다 확인한 경우
        if 조건을 만족하면:
            # 정답 처리
        return

    # 2. 경우 나누기 (백트래킹)
    # 현재 원소를 사용하는 경우
    dfs(n+1, sm + lst[n], cnt + 1)

    # 현재 원소를 사용하지 않는 경우
    dfs(n+1, sm, cnt)

# 초기 호출
dfs(0, 0, 0)

3. 예시 코드: 부분집합의 합이 특정 값이 되는 경우 찾기

• 주어진 배열에서 특정 합이 되는 부분집합을 찾는 문제를 백트래킹으로 해결하는 방식입니다.

# 예시: 주어진 배열에서 원소들의 합이 target과 같은 부분집합 찾기
lst = [1, 2, 3, 4, 5]
target = 10

def dfs(n, sm, cnt):
    # 1. 종료 조건: 배열의 끝에 도달한 경우
    if n == len(lst):
        if sm == target:  # 합이 target과 같은 경우
            print(f"합이 {target}이 되는 부분집합 발견: {cnt}개 원소 사용")
        return

    # 2. 현재 원소를 사용하는 경우
    dfs(n+1, sm + lst[n], cnt + 1)  # 원소 사용, 합에 더하고 원소 개수 증가

    # 3. 현재 원소를 사용하지 않는 경우
    dfs(n+1, sm, cnt)  # 원소 사용하지 않음, 그대로 진행

# 탐색 시작
dfs(0, 0, 0)

3-1. 전체 백트래킹 설명:

1. 트리 구조로 표현: 배열의 각 원소를 트리의 각 단계로 보고, 그 원소를 포함할지 말지에 따라 좌우로 분기합니다.
   • 트리의 각 레벨은 배열의 한 요소를 나타냅니다.
   • 왼쪽 분기는 그 원소를 포함하는 경우, 오른쪽 분기는 포함하지 않는 경우입니다.

2. DFS 함수:
   • dfs(n, sm, cnt)에서:
     • n은 배열의 인덱스 (현재 확인 중인 원소 위치)
     • sm은 지금까지의 원소 합계
     • cnt는 지금까지 사용한 원소의 개수
   • 종료 조건은 n == len(lst)로 모든 원소를 다 확인한 경우이며, 이때 합계가 target과 같은지 확인합니다.

3. 재귀 호출:
   • dfs(n+1, sm + lst[n], cnt + 1)는 현재 원소를 더하는 경우이며,
   • dfs(n+1, sm, cnt)는 현재 원소를 사용하지 않는 경우입니다.

4. Pruning (가지치기): 조건을 만족하지 않으면 더 깊이 탐색하지 않고 바로 되돌아오도록 구현할 수 있습니다. 예를 들어, sm > target인 경우는 더 이상 탐색하지 않아도 되는 경우입니다.

   if sm > target:
       return