[파이썬] 백트래킹 (Backtracking) 알고리즘의 구현과 활용

01 Sep 2023

python

백트래킹 알고리즘은 주어진 문제의 가능한 모든 해를 탐색하면서 최적의 해를 찾는 기법입니다. 이 알고리즘은 성능을 향상시키기 위해 가지치기 (Pruning) 과정을 통해 후보 해의 집합을 줄이는 특징을 가지고 있습니다. 이번 포스트에서는 백트래킹 알고리즘의 구현과 활용을 파이썬으로 살펴보겠습니다.

백트래킹 알고리즘의 구현

백트래킹 알고리즘은 깊이 우선 탐색 (Depth-First Search, DFS) 의 변형인데, 다음과 같이 구현할 수 있습니다.

def backtracking(state, choices):
    # 종료 조건
    if is_solution(state):
        process_solution(state)
        return

    for choice in choices:
        if is_valid(choice):
            make_move(choice)
            backtracking(state, choices)
            undo_move(choice)

위 코드는 백트래킹 알고리즘의 일반적인 구조입니다. state는 현재 상태를 나타내는 인자이고, choices는 선택할 수 있는 후보 해들입니다. is_solution 함수는 주어진 상태가 문제의 해인지 여부를 판단하고, process_solution 함수는 문제의 해에 대한 처리를 할 때 사용합니다. is_valid 함수는 선택한 후보 해가 유효한지를 판단하고, make_move 함수는 선택한 후보 해를 현재 상태에 반영합니다. undo_move 함수는 선택한 후보 해의 반영을 취소하는 역할을 합니다.

백트래킹 알고리즘의 활용

백트래킹 알고리즘은 다양한 문제들에 적용될 수 있습니다. 여기서는 대표적인 예시를 소개하겠습니다.

1. N-Queens 문제

N-Queens 문제는 N개의 퀸을 N x N 체스판에 배치하는 문제입니다. 퀸은 상하좌우 및 대각선 방향으로 이동할 수 있으며, 서로 공격할 수 없는 위치에 배치해야 합니다.

def is_valid(choice, queens):
    row, col = choice
    for i in range(row):
        if queens[i] == col or abs(queens[i] - col) == row - i:
            return False
    return True

def backtracking(n, row, queens):
    if row == n:
        process_solution(queens)
        return

    for col in range(n):
        choice = (row, col)
        if is_valid(choice, queens):
            queens[row] = col
            backtracking(n, row + 1, queens)
            queens[row] = -1

위 코드는 N-Queens 문제를 백트래킹 알고리즘으로 해결하기 위한 코드입니다. queens 리스트는 각 행에 퀸이 위치한 열을 저장하는 역할을 합니다. is_valid 함수는 선택한 후보가 유효한지를 판단하고, backtracking 함수는 퀸을 하나씩 배치해가면서 가능한 모든 해를 탐색합니다.

2. 스도쿠 문제

스도쿠 문제는 9 x 9 크기의 격자판에 숫자를 채우는 문제입니다. 모든 행, 열, 3 x 3 서브그리드에는 1부터 9까지의 숫자가 중복되지 않게 채워져야 합니다.

def is_valid(choice, board):
    row, col, num = choice

    for i in range(9):
        if board[row][i] == num or board[i][col] == num:
            return False

    subgrid_row = (row // 3) * 3
    subgrid_col = (col // 3) * 3
    for i in range(3):
        for j in range(3):
            if board[subgrid_row + i][subgrid_col + j] == num:
                return False

    return True

def backtracking(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    choice = (row, col, num)
                    if is_valid(choice, board):
                        board[row][col] = num
                        if backtracking(board):
                            return True
                        board[row][col] = 0
                return False

    return True

위 코드는 스도쿠 문제를 백트래킹 알고리즘으로 해결하기 위한 코드입니다. board는 스도쿠 판을 나타내는 2차원 리스트입니다. is_valid 함수는 선택한 후보가 유효한지를 판단하고, backtracking 함수는 빈 칸을 하나씩 채워가면서 가능한 모든 해를 탐색합니다.

정리

백트래킹 알고리즘은 가능한 모든 해를 탐색하면서 최적의 해를 찾는 기법으로, 가지치기 과정을 통해 후보 해의 집합을 줄입니다. 이번 포스트에서는 백트래킹 알고리즘의 구현과 활용을 파이썬으로 설명했습니다. N-Queens 문제와 스도쿠 문제는 백트래킹 알고리즘을 활용한 대표적인 예시입니다. 백트래킹 알고리즘을 적절히 사용하면 문제의 해를 효율적으로 찾을 수 있습니다.