[Algorithm/알고리즘] Backtracking - 백트래킹 알고리즘 이해하기

백트래킹(Backtracking) 알고리즘 이해하기

안녕하세요! 오늘은 백트래킹(Backtracking) 알고리즘에 대해 알아보겠습니다. 백트래킹은 문제를 해결하는 과정에서 가능한 모든 경우의 수를 탐색하는 방법 중 하나입니다. 예제와 함께 백트래킹을 이해해 봅시다.

백트래킹이란?

백트래킹은 문제 해결을 위해 모든 가능한 선택지를 탐색하면서, 잘못된 선택지가 발견되면 이전 단계로 돌아가서 다른 선택지를 시도하는 알고리즘입니다. 이를 통해 최종적으로 문제를 해결할 수 있는 올바른 선택지를 찾습니다. 마치 미로에서 출구를 찾기 위해 여러 길을 시도하는 것과 비슷합니다. 이 방법은 미로 찾기, 스도쿠 퍼즐, N-퀸 문제 등 다양한 문제를 해결하는 데 사용됩니다.

백트래킹의 동작 원리

1. 초기 상태에서 출발: 문제 해결을 시작합니다.
2. 가능한 모든 선택지 시도: 현재 상태에서 가능한 모든 선택지를 시도합니다.
3. 조건 만족 확인: 선택지가 유효한지 확인합니다.
4. 조건 만족 시 계속 진행: 유효한 선택지라면 다음 단계로 진행합니다.
5. 조건 불만족 시 되돌아가기: 유효하지 않다면 이전 단계로 돌아가 다른 선택지를 시도합니다.

백트래킹은 재귀(Recursion)를 이용하여 각 단계에서 가능한 선택지를 탐색합니다. 이 과정에서 유효한 선택지인지 확인하고, 유효하지 않다면 다시 돌아가 다른 선택지를 시도하는 방식입니다.

예제 코드: N-퀸 문제

N-퀸 문제는 N x N 체스판에 N개의 퀸을 서로 공격하지 않게 배치하는 문제입니다. 백트래킹을 이용해 해결해 보겠습니다.

def is_safe(board, row, col):
    # 주어진 열(col)에 이미 퀸이 있는지 확인
    for i in range(row):
        if board[i][col] == 1:
            return False
    
    # 왼쪽 상단 대각선 확인
    i, j = row, col
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1
    
    # 오른쪽 상단 대각선 확인
    i, j = row, col
    while i >= 0 and j < len(board):
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1
    
    # 퀸을 놓을 수 있는 안전한 위치이면 True 반환
    return True

def solve_n_queens(board, row):
    # 모든 퀸을 다 배치했으면 True 반환
    if row >= len(board):
        return True
    
    # 현재 행(row)에서 모든 열(col)을 확인
    for col in range(len(board)):
        # 퀸을 놓을 수 있는 안전한 위치인지 확인
        if is_safe(board, row, col):
            # 퀸 배치
            board[row][col] = 1
            # 다음 행에 퀸을 배치할 수 있는지 확인
            if solve_n_queens(board, row + 1):
                return True
            # 배치할 수 없다면 퀸을 제거(백트래킹)
            board[row][col] = 0
    
    # 현재 행(row)에 퀸을 배치할 수 있는 위치가 없다면 False 반환
    return False

def print_board(board):
    # 보드 출력
    for row in board:
        print(" ".join(str(x) for x in row))

# 보드 크기
n = 4
# n x n 크기의 보드를 0으로 초기화
board = [[0] * n for _ in range(n)]

# 첫 번째 행부터 퀸 배치를 시작
if solve_n_queens(board, 0):
    print_board(board)
else:
    print("해결책이 없습니다.")

코드 설명

1. is_safe 함수:
   • 특정 위치 (row, col)에 퀸을 놓을 수 있는지 확인합니다.
   • 현재 열과 왼쪽 및 오른쪽 대각선 방향에 다른 퀸이 있는지 검사합니다.
   • 퀸을 놓을 수 있는 위치라면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
2. solve_n_queens 함수:
   • 재귀적으로 퀸을 보드에 배치하는 함수입니다.
   • 현재 행의 모든 열에 대해 퀸을 놓을 수 있는지 확인하고, 안전하다면 퀸을 놓습니다.
   • 다음 행에 대해 재귀적으로 퀸을 배치하고, 만약 모든 퀸을 성공적으로 배치했다면 True를 반환합니다.
   • 현재 행에 퀸을 놓을 수 있는 위치가 없다면 False를 반환합니다.
3. print_board 함수:
   • 현재 보드 상태를 출력합니다. 1은 퀸이 놓인 위치를, 0은 빈 칸을 나타냅니다.
4. 보드 초기화 및 해결 시작:
   • n 크기의 보드를 0으로 초기화합니다.
   • solve_n_queens 함수를 호출하여 첫 번째 행부터 퀸을 배치합니다.
   • 해결 가능한 경우 보드를 출력하고, 불가능한 경우 "해결책이 없습니다."를 출력합니다.

이 코드는 N-Queen 문제를 백트래킹 기법을 사용하여 해결합니다. 각 행마다 퀸을 하나씩 배치하며, 유효하지 않은 배치는 백트래킹을 통해 되돌아가며 해결책을 찾습니다.

실제 사용 예시

백트래킹 알고리즘은 다양한 문제 해결에 사용됩니다. 예를 들어:

1. 미로 찾기: 미로에서 출구를 찾는 문제.
2. 수수께끼 풀기: 스도쿠 같은 퍼즐 문제 해결.
3. 조합 찾기: 특정 조건을 만족하는 모든 조합 찾기 (예: 부분 집합 합 문제).

결론

백트래킹은 가능한 모든 경우의 수를 탐색하여 문제를 해결하는 강력한 알고리즘입니다. 비록 시간이 오래 걸릴 수 있지만, 정확한 해답을 찾을 수 있는 장점이 있습니다. 여러 가지 예제를 통해 백트래킹의 동작 방식을 직접 체험해 보세요. 이를 통해 문제 해결 능력을 크게 향상시킬 수 있을 것입니다.

백트래킹 알고리즘은 컴퓨터 과학의 다양한 분야에서 널리 사용되며, 복잡한 문제를 해결하는 데 매우 유용한 도구입니다. 이번 기회를 통해 백트래킹에 대해 이해하고, 실제 문제에 적용해 보시기 바랍니다.