백 트래킹

백 트래킹(Backtracking)

해를 찾는 도중에 막히면 되돌아가서 다시 해를 찾아가는 기법으로 모든 가능한 경우를 체계적으로 탐색합니다.

 

# N-Queens 문제
def solve_n_queens(n):
    def is_safe(board, row, col):
        # 같은 열에 다른 퀸이 있는지 확인
        for i in range(row):
            if board[i] == col:
                return False
        
        # 대각선에 다른 퀸이 있는지 확인
        for i in range(row):
            if abs(board[i] - col) == abs(i - row):
                return False
        
        return True
    
    def backtrack(board, row):
        if row == n:
            return [board[:]]
        
        solutions = []
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                solutions.extend(backtrack(board, row + 1))
                board[row] = -1  # 백트래킹
        
        return solutions
    
    return backtrack([-1] * n, 0)

# 조합 생성 (백트래킹)
def generate_combinations(arr, r):
    def backtrack(start, current_combination):
        if len(current_combination) == r:
            result.append(current_combination[:])
            return
        
        for i in range(start, len(arr)):
            current_combination.append(arr[i])
            backtrack(i + 1, current_combination)
            current_combination.pop()  # 백트래킹
    
    result = []
    backtrack(0, [])
    return result

# 순열 생성 (백트래킹)
def generate_permutations(arr):
    def backtrack(current_permutation):
        if len(current_permutation) == len(arr):
            result.append(current_permutation[:])
            return
        
        for num in arr:
            if num not in current_permutation:
                current_permutation.append(num)
                backtrack(current_permutation)
                current_permutation.pop()  # 백트래킹
    
    result = []
    backtrack([])
    return result

# 미로 찾기
def solve_maze(maze):
    n = len(maze)
    m = len(maze[0])
    solution = [[0 for _ in range(m)] for _ in range(n)]
    
    def is_safe(x, y):
        return 0 <= x < n and 0 <= y < m and maze[x][y] == 1
    
    def backtrack(x, y):
        if x == n - 1 and y == m - 1:
            solution[x][y] = 1
            return True
        
        if is_safe(x, y):
            solution[x][y] = 1
            
            # 오른쪽으로 이동
            if backtrack(x, y + 1):
                return True
            
            # 아래로 이동
            if backtrack(x + 1, y):
                return True
            
            # 백트래킹
            solution[x][y] = 0
            return False
        
        return False
    
    if backtrack(0, 0):
        return solution
    else:
        return None

# 예제
# N-Queens 문제 (4x4)
solutions = solve_n_queens(4)
print(f"4-Queens 해의 개수: {len(solutions)}")
if solutions:
    print(f"첫 번째 해: {solutions[0]}")

# 조합 생성
combinations = generate_combinations([1, 2, 3, 4], 2)
print(f"조합 C(4,2): {combinations}")

# 순열 생성
permutations = generate_permutations([1, 2, 3])
print(f"순열 P(3): {permutations}")

# 미로 찾기
maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]
]
solution = solve_maze(maze)
if solution:
    print("미로 해결 경로:")
    for row in solution:
        print(row)
else:
    print("미로를 해결할 수 없습니다.")