[알고리즘]백트래킹(BackTracking)

ChaeHyeong·2024년 8월 19일

개념 백트래킹 알고리즘

알고리즘 & 자료구조

목록 보기

4/6

백트래킹(BackTracking)

1. BackTracking Algorithm이란?

모든 가능한 해를 탐색하는 과정에서, 조건에 맞지 않는 경우 더 이상 탐색을 진행하지 않고 이전 단계로 되돌아가서 다른 경로를 탐색하는 알고리즘이다.
백트래킹은 문제 해결 과정에서 잘못된 선택을 빠르게 배제할 수 있어, 효율적으로 해를 구할 수 있다.
백트래킹은 주로 탐색 공간이 매우 크거나 해결책이 여러 개 존재하는 문제에서 유용하게 사용됩니다.

2. BackTracking 조건

상태 공간 트리(State Space Tree)
- 백트래킹 문제를 해결할 때 가능한 모든 경로를 상태 공간 트리로 표현할 수 있습니다.
- 각 노드는 상태를 나타내고, 백트래킹은 이 트리를 순회하면서 해를 찾습니다.
유망성(Promising)
- 각 단계에서 탐색을 계속할지 말지 결정하는 기준이 필요합니다.
- 이 조건을 만족하지 않는 경우, 더 깊이 탐색하지 않고 이전 단계로 돌아갑니다.
해를 찾으면 종료
- 해를 찾으면 그 시점에서 탐색을 종료할 수 있습니다.
- 경우에 따라 모든 해를 찾아야 하는 경우도 있지만, 첫 번째 해를 찾으면 바로 종료하는 방식도 있습니다.

3. BackTracking 동작 방식

해를 찾기 위한 시도: 문제를 해결하기 위해 가능한 모든 선택을 시도합니다.
유망성 확인: 현재 상태가 유망한지 확인합니다. 만약 더 이상 유망하지 않다면 해당 경로를 더 이상 탐색하지 않고 돌아갑니다.
백트래킹: 유망하지 않은 경로를 빠르게 배제하고, 다른 경로를 시도합니다. 이 과정을 통해 탐색 시간을 줄일 수 있습니다.

4. 백트래킹(BackTracking) vs 깊이 우선 탐색(DFS)

DFS(Depth-First Search)와 백트래킹(Backtracking)은 모두 탐색 알고리즘에서 사용되는 기법입니다.

이 둘은 겉으로 보기에는 유사하지만, 본질적인 차이가 있습니다. 아래에서 차이와 공통점을 정리해 보겠습니다.

4-1. 공통점

재귀적 탐색: 두 알고리즘 모두 재귀를 통해 상태를 탐색합니다. DFS는 그래프나 트리의 깊이를 우선적으로 탐색하는 방식이고, 백트래킹 역시 재귀적으로 문제를 해결하는 과정에서 특정 경로를 탐색합니다.
완전 탐색: DFS와 백트래킹 모두 완전 탐색 알고리즘으로, 탐색 공간을 완전히 탐색하여 해를 찾는 것을 목표로 합니다.
상태 공간 트리: 두 알고리즘 모두 상태 공간 트리를 탐색하며, 각각의 상태가 문제의 해를 나타낼 수 있는지 확인합니다.

4-2. 차이점

목적
DFS
- DFS는 주로 그래프 탐색에서 사용되며, 특정 노드에 도달하거나 모든 경로를 탐색하는 것을 목표로 합니다.
- DFS는 탐색의 깊이를 우선적으로 다루고, 경로를 모두 끝까지 탐색한 후에 다음 경로로 넘어갑니다.

백트래킹
- 백트래킹은 특정 조건을 만족하는 해를 찾는 문제에서 사용되며, 유망하지 않은 경로는 미리 배제하는 방식입니다.
- 불필요한 경로를 탐색하지 않도록 조건을 설정해 효율성을 높입니다.

유망성 확인
DFS
- 모든 경로를 탐색하는 것이 목적이므로 경로가 유망한지 여부를 따지지 않고 끝까지 탐색합니다.

백트래킹
- 유망성 조건을 확인하여 불필요한 탐색을 피합니다.
- 탐색 도중에 조건이 맞지 않으면 더 깊이 탐색하지 않고, 그 경로를 중단하고 다른 경로를 탐색합니다.

적용 범위:
DFS
- 주로 그래프 탐색이나 트리 탐색 문제에서 사용되며, 경로를 찾거나 그래프의 특정 속성을 탐색할 때 사용됩니다.

백트래킹
- 주로 퍼즐 문제(예: N-Queens, Sudoku), 최적화 문제 등에서 사용되며, 조건에 맞는 해를 찾아내는 데 주로 사용됩니다.

4-3. 장단점

DFS
- 장점 -
1. 단순성: DFS는 간단한 구현이 가능하며, 그래프나 트리 탐색 문제에서 기본적으로 사용됩니다.
2. 메모리 효율성: 깊이 우선 탐색은 하나의 경로만 저장하므로, 메모리 사용량이 비교적 적습니다.

- 단점 -
1. 비효율성: 모든 경로를 끝까지 탐색하므로, 불필요한 경로까지 모두 탐색해야 합니다. 최적해를 찾기 위해서는 모든 경로를 살펴야 하므로 시간 복잡도가 높아질 수 있습니다.
2. 무한 루프 가능성**: 사이클이 있는 그래프에서 처리하지 않으면 무한 루프에 빠질 수 있습니다.

백트래킹
- 장점 -
1. 효율성: 유망하지 않은 경로를 미리 배제하므로, 전체 탐색 시간과 자원을 절약할 수 있습니다.
2. 다양한 문제 해결 가능: 퍼즐, 최적화 문제 등 다양한 문제에서 효과적으로 사용됩니다.

- 단점 -
1. 복잡한 구현: 유망성 조건을 정확히 설정해야 하므로, 문제에 따라 구현이 복잡할 수 있습니다.
2. 시간 복잡도: 최악의 경우 모든 경로를 탐색해야 할 수도 있으며, 이 경우 시간 복잡도가 DFS와 동일하게 비효율적일 수 있습니다.

5. 백트래킹 예시

- 예시 : [1 , 2, 3] 배열의 모든 순열을 구하시오.

def permute(nums):
    result = []
    visited = [False] * len(nums)  # 각 숫자의 사용 여부를 추적
    
    def backtrack(path):
        if len(path) == len(nums):
            result.append(' '.join(map(str, path)))  # 경로가 완성되면 문자열로 변환해 결과에 추가
            return
        for i in range(len(nums)):
            if not visited[i]:  # 아직 사용되지 않은 숫자만 선택
                visited[i] = True  # 숫자를 사용 처리
                path.append(nums[i])  # 경로에 숫자 추가
                backtrack(path)  # 다음 숫자 선택
                path.pop()  # 백트래킹: 선택을 취소
                visited[i] = False  # 숫자를 다시 사용 가능하게 설정
    
    backtrack([])  # 빈 경로에서 시작
    return result  # 문자열 형식으로 된 결과 리스트 반환

# 사용 예시
nums = [1, 2, 3]
permutations = permute(nums)
for perm in permutations:
    print(perm)

초기 설정:
- visited: 각 숫자의 사용 여부를 추적하는 리스트입니다.
- backtrack(path): 숫자를 선택하며 순열을 생성하는 재귀 함수입니다.
재귀 호출:
- path의 길이가 숫자 리스트 nums의 길이와 같아지면, 하나의 순열이 완성된 것입니다. 이때, 완성된 순열을 결과 리스트에 추가합니다.
- 숫자 리스트를 순회하면서 아직 사용되지 않은 숫자를 선택하고, 경로(path)에 추가한 후 다음 숫자를 선택하는 재귀 호출을 진행합니다.
백트래킹:
- 재귀 호출이 종료되면 마지막으로 추가한 숫자를 경로에서 제거(pop())하고, 해당 숫자를 다시 사용 가능하도록 설정하여 다른 순열을 생성합니다.

6. 백트래킹 사용 시 유의 사항

유망성 조건 설정: 백트래킹의 핵심은 “유망성”을 확인하는 과정입니다. 불필요한 탐색을 줄이기 위해, 가능한 빨리 유망하지 않은 경로를 배제하는 조건을 설정해야 합니다.
재귀 깊이 주의: 재귀 호출이 너무 깊어지면 스택 오버플로우가 발생할 수 있습니다. 문제의 크기가 커질 경우, 반복문을 사용하는 방식으로 전환하는 것도 고려해야 합니다.
메모이제이션 활용: 백트래킹 과정에서 동일한 하위 문제를 여러 번 해결하게 되는 경우가 많습니다. 이때 메모이제이션 기법을 적용하여 중복 계산을 방지하면 성능을 개선할 수 있습니다.