백트래킹(Backtracking)

백트래킹(Backtracking)은 탐색 알고리즘의 하나로, 모든 가능한 경우의 수를 탐색하면서도 불필요한 탐색을 줄이는 방법입니다. 이를 통해 효율적으로 정답을 찾아낼 수 있습니다.

백트래킹의 핵심 아이디어

• 모든 경우의 수를 탐색: 가능한 모든 해를 탐색하는 과정을 포함합니다.
• 가지치기(Pruning): 탐색 도중 현재 경로가 유망하지 않다고 판단되면, 해당 경로를 더 이상 탐색하지 않고 되돌아가는 방식입니다.

백트래킹의 특징

1. 완전 탐색 기반:
   • 백트래킹은 기본적으로 모든 경우를 탐색하지만, 불필요한 탐색을 피할 수 있습니다.
2. 재귀를 활용:
   • 대부분 재귀적으로 구현되며, 상태를 저장하고 탐색이 종료되면 이전 상태로 돌아갑니다.
3. 유망성 판단:
   • 탐색 도중 "이 경로는 정답이 될 가능성이 없다"고 판단되면 해당 경로를 탐색하지 않고 중단(Pruning)합니다.

백트래킹 동작 과정

1. 현재 상태에서 가능한 모든 후보를 시도:
   • 모든 후보 중 하나를 선택하여 탐색을 진행합니다.
2. 유망한 후보만 탐색:
   • 선택한 후보가 문제의 조건을 만족하지 않으면 탐색을 중단하고 되돌아갑니다.
3. 탐색 완료 후 되돌아가기:
   • 재귀적으로 탐색을 마치면 다시 이전 상태로 되돌아가 다른 후보를 시도합니다.

백트래킹 구현 구조

기본 재귀 구조

def backtrack(path, state):
    if 조건 만족:  # 종료 조건
        정답 처리
        return

    for 후보 in 후보군:
        if 유망한지 검사(Pruning):
            상태 갱신
            backtrack(갱신된 path, 갱신된 state)
            상태 복원

백트래킹 예제

1. N-Queens 문제

• 문제: N×N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치.
• 풀이: 백트래킹을 통해 한 행씩 퀸을 놓아보며 조건을 만족하는 경우를 탐색.

def is_safe(board, row, col, n):
    # 위쪽과 대각선을 검사
    for i in range(row):
        if board[i] == col or abs(board[i] - col) == abs(i - row):
            return False
    return True

def n_queens(n, row=0, board=[]):
    if row == n:  # 모든 퀸을 배치한 경우
        print(board)  # 정답 출력
        return
    
    for col in range(n):  # 현재 행에서 모든 열을 시도
        if is_safe(board, row, col, n):  # 유망한지 검사
            board.append(col)  # 퀸 배치
            n_queens(n, row + 1, board)  # 다음 행으로 이동
            board.pop()  # 상태 복원

# 4-Queens 문제 실행
n_queens(4)

2. 부분집합 구하기

• 문제: 주어진 배열에서 가능한 모든 부분집합을 구하시오.
• 풀이: 각 요소를 포함하거나 포함하지 않는 두 가지 경우로 탐색.

def subsets(nums, index=0, path=[]):
    if index == len(nums):  # 모든 요소를 검사한 경우
        print(path)  # 현재 부분집합 출력
        return

    # 현재 요소를 포함하지 않는 경우
    subsets(nums, index + 1, path)

    # 현재 요소를 포함하는 경우
    subsets(nums, index + 1, path + [nums[index]])

# 예제 실행
subsets([1, 2, 3])

백트래킹과 DFS의 차이

특징                     DFS                             백트래킹

탐색 범위	모든 경로 탐색	조건에 따라 일부 경로 제외 (가지치기)
종료 조건	모든 경로를 탐색한 후 종료	유망하지 않은 경로는 조기 종료
활용	모든 경우를 탐색	최적화된 탐색
예제 문제	그래프 탐색	N-Queens, 순열, 조합, 수식 계산 문제

백트래킹의 시간 복잡도

• 시간 복잡도는 경우에 따라 다르며, 최악의 경우 모든 경로를 탐색해야 하므로 지수 시간 복잡도를 가질 수 있습니다.
• 하지만, 가지치기(Pruning)를 통해 탐색 범위를 줄이면 실제 실행 시간은 훨씬 줄어듭니다.

백트래킹 활용 사례

1. N-Queens 문제: N×NN \times NN×N 체스판에서 퀸 배치.
2. 순열 및 조합 생성: 모든 가능한 순열, 조합을 생성.
3. 부분집합 생성: 모든 부분집합을 구하는 문제.
4. 수식 계산: 연산자나 피연산자를 조합하여 특정 값 생성.
5. 미로 탐색: 특정 조건을 만족하는 경로 찾기.
6. 스도쿠 해결: 스도쿠 퍼즐의 해답 찾기.

정리

• 백트래킹은 모든 경우를 탐색하면서도 가지치기를 통해 효율성을 높이는 방법입니다.
• 재귀를 기반으로 구현되며, 특정 조건을 만족하지 않는 경로를 빠르게 제외(Pruning)하여 탐색을 줄입니다.
• 알고리즘 문제 해결에서 백트래킹은 최적의 해를 찾아야 하는 문제에서 매우 유용합니다