백트래킹: 완전 탐색, 가지 치기

백트래킹은 해를 구성해 나가는 과정에서 유망하지 않은 경로를 조기에 배제함으로써, 전체 탐색 공간을 줄여주는 방법입니다. 이 과정에서 가지치기를 통해, 불필요한 계산을 줄이면서 최적의 해를 찾는 과정을 반복합니다.

백트래킹의 대표적인 활용 예시는 다음과 같습니다:

• 미로 찾기: 출발점에서 도착점까지 가는 경로를 찾되, 막다른 길에서는 탐색을 중단합니다.
• N-Queen 문제: N x N 체스판에서 N개의 퀸을 서로 공격하지 않도록 배치하는 방법을 찾습니다.
• 조합 최적화 문제: 최소 비용 경로, 최대 이익 경로 등 최적화가 필요한 문제를 해결할 때 사용됩니다.

시간 복잡도: 백트래킹의 시간 복잡도는 탐색해야 할 모든 경우의 수에 따라 결정되며, 보통 경우의 수가 많아질수록 탐색 시간도 기하급수적으로 증가합니다. 그러나 가지치기 기법을 통해 경우의 수를 줄이면 탐색 시간을 효과적으로 줄일 수 있습니다.

백트래킹의 효율성을 높이기 위해 사용하는 가지치기 기법은, 현재 경로가 해를 찾을 가능성이 없다고 판단되면 해당 경로의 탐색을 중단하는 방법입니다. 이를 통해 탐색 공간을 줄이고, 불필요한 연산을 방지합니다.

가지치기의 조건: 가지치기 기법은 유망성을 판단할 수 있을 때 적용 가능합니다. 유망성 판단을 위한 조건이 설정되면, 탐색 공간을 큰 폭으로 줄일 수 있습니다.

N-Queen 문제는 N x N 체스판에서 N개의 퀸이 서로 공격하지 않도록 배치하는 문제입니다. 백트래킹을 사용하여 모든 경우를 탐색하고 가지치기를 통해 효율적으로 해결할 수 있습니다.

문제 정의: 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 방법을 찾으세요. 퀸은 같은 행, 열, 대각선에 다른 퀸이 있으면 공격할 수 있습니다.

풀이 접근:

• 1️⃣ 체스판의 각 행에 한 개의 퀸을 배치하여, N개의 퀸을 배치합니다.
• 2️⃣ 각 행에 퀸을 배치할 때, 같은 열이나 대각선에 다른 퀸이 없는지 확인합니다.
• 3️⃣ 조건을 만족하지 않는 경우, 가지치기를 통해 해당 경로를 탐색에서 제외합니다.

Python 코드 예제:
def is_safe(board, row, col, n):
    # 같은 열에 있는 퀸 확인
    for i in range(row):
        if board[i] == col or \
           board[i] - i == col - row or \
           board[i] + i == col + row:
            return False
    return True

def solve_n_queens(board, row, n):
    if row == n:
        print(board)  # 해결된 퀸 배치 출력
        return

    for col in range(n):
        if is_safe(board, row, col, n):
            board[row] = col
            solve_n_queens(board, row + 1, n)
            board[row] = -1  # 백트래킹

# N-Queen 문제 실행
n = 4
board = [-1] * n
solve_n_queens(board, 0, n)
                

설명: solve_n_queens 함수는 백트래킹을 통해 모든 가능한 퀸의 배치를 탐색합니다. 각 퀸의 배치를 시도하고, 충돌이 발생하는 경우 가지치기를 통해 탐색을 중단합니다. 이때 is_safe 함수는 현재 배치가 안전한지를 판단하여 유망성을 확인합니다.