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

2024-11-05 14:59:11 | 조회수 95


백트래킹: 완전 탐색과 가지치기 기법 🌿

백트래킹(Backtracking)은 해를 찾기 위해 모든 가능한 경우의 수를 탐색하는 방법으로, 불필요한 경로를 줄이기 위해 가지치기(pruning) 기법을 사용하는 탐색 알고리즘입니다. 백트래킹은 DFS(깊이 우선 탐색)을 기반으로 작동하며, 최적화 문제 및 조합 문제에서 효과적으로 사용됩니다.

1. 백트래킹의 개념 🌍

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

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

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

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

2. 가지치기 기법의 원리와 적용 🌳

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

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

3. 백트래킹 예제: N-Queen 문제 🏰

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 함수는 현재 배치가 안전한지를 판단하여 유망성을 확인합니다.

이번 글에서는 백트래킹의 기본 개념과 가지치기 기법을 배우고, 대표적인 예제인 N-Queen 문제를 통해 적용 방법을 학습했습니다. 백트래킹을 통해 최적의 해를 찾는 연습을 지속하여 다양한 문제를 해결해 보세요!


백트래킹: 완전 탐색, 가지 치기 - 알고리즘닷컴 19 개의 글