Backtracking

백트래킹은 단순히 되돌아가는 것을 넘어, 상태 공간 트리(State Space Tree)를 체계적으로 탐색하며 해답을 찾는 강력한 알고리즘

⭐ Backtracking의 특징

✅ 1. 깊이 우선 탐색(DFS) 기반

• 백트래킹은 상태 공간 트리를 깊이 우선 탐색(DFS) 방식으로 탐색
• 현재 경로를 따라 끝까지 진행하다가 더 이상 해답이 될 수 없는 상황에 이르면 이전 단계로 돌아와 다른 경로를 탐색

DFS(Depth-First Search)란?

• https://velog.io/@00_deidre_00/DFS-Depth-First-Search

✅ 2. 유망성 검사 (Promising Check)

• 현재 경로가 해답으로 이어질 가능성이 있는지 검사합니다. 만약 해가 될 수 없다고 판단되면 더 이상 그 경로를 탐색하지 않고 즉시 되돌아감. 이를 가지치기(Pruning)라고 함

✅ 3. 재귀 호출

• 재귀 함수를 통해 구현되는 경우가 많음
• 각 재귀 호출은 상태 공간 트리의 한 단계 깊이로 이동하는 것을 의미

---

📌 Backtracking의 단계

✅ 1. 초기 상태

• 문제의 초기 상태를 나타내는 루트 노드에서 탐색을 시작

✅ 2. 후보 선택

• 현재 상태에서 다음 결정을 내릴 수 있는 모든 후보를 고려

✅ 3. 유망성 검사

• 선택한 후보가 해답으로 이어질 가능성이 있는지 확인

✅ 4. 다음 단계 이동

• 만약 유망하다면, 해당 후보를 포함한 새로운 상태로 이동하여 다음 단계의 탐색을 계속 (재귀 호출)

✅ 5. Backtracking

• 만약 후보가 유망하지 않거나, 현재 경로의 끝에 도달했으나 해답을 찾지 못했다면, 이전 상태로 되돌아와 다른 후보를 선택

✅ 6. 종료

• 모든 가능한 경로를 탐색하거나 해답을 찾을 때까지 이 과정을 반복

---

❗ Backtracking의 구현

✅ 1. 재귀 호출을 이용한 구현

• 백트래킹은 재귀 함수를 사용하여 구현되는 경우가 많음

• 함수는 현재 상태를 인자로 받고, 다음 단계의 모든 후보를 순회하며 자기 자신을 재귀적으로 호출

• 함수 구조

function backtrack(current_state):
    if is_solution(current_state):
        save_solution(current_state)
        return

    for next_candidate in get_candidates(current_state):
        if is_promising(next_candidate):
            backtrack(next_candidate)

✅ 2. 상태 저장 및 복원

• 재귀 호출이 끝난 후, 다음 후보를 탐색하기 위해 이전 상태로 돌아가야 함
• 이는 함수가 반환될 때 자동으로 이루어지거나, 명시적으로 상태를 복원하는 코드를 작성하여 구현

---

⚠️ Backtracking의 장단점

✅ 장점

• 모든 해답 찾기: 가지치기 기능을 통해 불필요한 탐색을 줄이면서도, 모든 가능한 해답을 찾을 수 있음
• 체계적 탐색: 상태 공간 트리를 깊이 우선 방식으로 체계적으로 탐색하여 문제를 효율적으로 해결

❌ 단점

• 높은 복잡도: 최악의 경우, 모든 가능한 경로를 탐색해야 하므로 시간 복잡도가 매우 높을 수 있음
• 가지치기 의존성: 알고리즘의 효율성은 '유망성 검사'를 통해 얼마나 효과적으로 가지치기를 수행하는지에 달려 있음

---

📝 예제

N × N 체스판에 N개의 퀸을 서로 공격할 수 없도록 놓는 모든 경우의 수를 찾는 함수

def solve_n_queens(n):
    # 해답을 저장할 리스트
    solutions = []
    # 현재 체스판 상태 (각 행의 퀸 위치를 저장)
    board = [-1] * n
    
    # 백트래킹 탐색 시작
    backtrack(0, n, board, solutions)
    return solutions

def backtrack(row, n, board, solutions):
    # 5. 해답: 모든 행에 퀸을 놓는 데 성공했다면, 해답을 찾은 것
    if row == n:
        solutions.append(board[:])
        return

    # 2. 다음 단계: 현재 행(row)의 모든 열(col)에 대해 퀸을 놓아보기
    for col in range(n):
        # 3. 유망성 검사: 현재 위치(row, col)가 유망한지 확인
        if is_promising(row, col, board):
            # 퀸을 현재 위치에 놓음
            board[row] = col
            # 4. 다음 행으로 이동하여 재귀 호출
            backtrack(row + 1, n, board, solutions)
            # 백트래킹이 일어난 후, 다음 열을 시도하기 위해 상태 복원
            # board[row]는 다음 반복에서 덮어쓰여지므로 명시적 복원 불필요

def is_promising(row, col, board):
    # 이전 행들을 검사하며 퀸의 위치를 확인
    for prev_row in range(row):
        # 같은 열에 퀸이 있는지 확인
        if board[prev_row] == col:
            return False
        # 대각선에 퀸이 있는지 확인 (row 간 거리 == col 간 거리)
        if abs(board[prev_row] - col) == abs(prev_row - row):
            return False
    return True

# 실행 예제: N=4인 경우
n = 4
solutions = solve_n_queens(n)

print(f"N = {n} 일 때, 총 {len(solutions)}개의 해답을 찾았습니다.")
for i, sol in enumerate(solutions):
    print(f"해답 {i+1}: {sol}")
    # 퀸이 놓인 체스판 시각화 (선택 사항)
    for r in range(n):
        row_str = ["."]*n
        row_str[sol[r]] = "Q"
        print(" ".join(row_str))
    print()

1. 시작: 첫 번째 행에 퀸을 놓는 위치를 결정
2. 다음 단계: 다음 행으로 이동하여 퀸을 놓을 수 있는 모든 열을 확인
3. 유망성 검사: 현재 위치가 유망한지(다른 퀸에게 공격받지 않는지) 확인
4. 백트래킹: 만약 유망하지 않다면, 현재 행의 다른 열로 이동하여 다시 시도. 모든 열을 시도했음에도 퀸을 놓을 수 없다면, 이전 행으로 돌아가(백트래킹) 다른 위치를 탐색.
5. 해답: N개의 퀸을 모두 성공적으로 놓으면 하나의 해답을 찾은 것

---

🔎 Backtracking의 주요 활용 예시

✅ 1. N-Queen 문제

N개의 퀸을 놓는 모든 해를 찾는 문제

✅ 2. 스도쿠

✅ 3. 조합(Combination) 문제

주어진 집합에서 특정 조건을 만족하는 모든 조합을 찾는 문제

✅ 4. 미로 찾기

미로의 출구를 찾는 모든 경로를 탐색하는 문제