[python] 백트래킹 알고리즘의 예시

07 Dec 2023

python

백트래킹(backtracking)은 조건을 검사하며 해를 찾는 알고리즘입니다. 이 알고리즘은 주어진 조건을 만족하는 해를 찾는 과정에서 불필요한 탐색을 줄임으로써 실행 시간을 단축시킬 수 있습니다.

예를 들어, 문제를 해결하는 데에 있어 ‘말판 위의 나이트(N-Knight)의 이동’이라는 조건이 있다고 가정해봅시다. 이때 나이트의 이동은 L 모양으로 이루어져 있으며, 말판 상에서 이동할 수 있는 모든 경우의 수를 찾아야 합니다.

def is_valid_move(board, row, col):
    if row >= 0 and row < len(board) and col >= 0 and col < len(board[0]) and board[row][col] == -1:
        return True
    return False

def solve_knight_tour(board, row, col, move_count):
    moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]

    if move_count == len(board) * len(board[0]):
        return True

    for move in moves:
        next_row = row + move[0]
        next_col = col + move[1]

        if is_valid_move(board, next_row, next_col):
            board[next_row][next_col] = move_count
            if solve_knight_tour(board, next_row, next_col, move_count + 1):
                return True

            board[next_row][next_col] = -1

    return False

def knight_tour(n):
    board = [[-1] * n for _ in range(n)]
    start_row, start_col = 0, 0
    board[start_row][start_col] = 0

    if solve_knight_tour(board, start_row, start_col, 1):
        return board

    return None

위의 예제는 재귀적인 백트래킹 알고리즘을 사용하여 나이트의 이동 문제를 해결하는 함수입니다. 함수 knight_tour(n)는 말판의 크기 n을 입력으로 받아, 조건을 만족하는 이동 경로를 반환합니다.

이 코드에서는 is_valid_move() 함수를 사용하여 주어진 조건을 만족하는지 확인하고, solve_knight_tour() 함수에서 해당 위치로 이동한 후 재귀적으로 탐색하며 모든 경우를 탐색합니다. 마지막으로, knight_tour() 함수에서는 시작 위치와 함께 solve_knight_tour() 함수를 호출하여 최종 결과를 반환하는 구조로 이루어져 있습니다.

참고문헌: