Back tracking

백트래킹 (Backtracking)

정의

• 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만을 찾아내는 기법입니다.
• 해결 과정에서 더 이상 진행이 불가능하다고 판단되면, 이전의 분기점으로 돌아가 다른 가능성을 탐색합니다.

사용 예

• 문제: N-Queen, 순열, 조합 등

과정 설명

1. 선택: 가능한 후보 중 하나를 선택합니다.
2. 제약 조건 검사: 선택이 문제의 제약 조건에 위배되는지 확인합니다.
3. 목표 확인: 현재 선택이 문제 해결의 목표에 도달했는지 확인합니다.
4. 불가능한 경우 백트래킹: 선택이 불가능하다면 이전 단계로 돌아갑니다.

Sudo Code

def is_safe(board, row, col):
    # 해당 위치에 퀸을 놓을 수 있는지 확인하는 함수

def solve_n_queen(board, col):
    if col >= N:
        return True

    for i in range(N):
        if is_safe(board, i, col):
            board[i][col] = 1
            if solve_n_queen(board, col + 1):
                return True
            board[i][col] = 0  # 백트래킹

    return False