백트래킹(Backtracking) 알고리즘

백트래킹은 일종의 DFS 기반 알고리즘으로, 문제 해결 과정에서 해를 찾기 위해 후보군을 검사하다가 조건을 만족하지 않으면 이전 단계로 돌아가 다른 후보군을 찾는 기법이다. 주로 조합, 순열, 부분집합 등을 구하는 문제에서 사용된다.

백트래킹은 유용한 문제 해결 기법 중 하나로, 많은 NP-hard 문제에 적용될 수 있다.

백트래킹의 기본 아이디어

1. 상태 공간 트리(State Space Tree): 문제의 해를 트리 구조로 표현한다. 각 노드는 문제의 한 상태를 나타내며, 간선은 상태 간의 전이를 나타낸다.
2. 프로모션(promising): 해당 노드에서 유망한지 검사한다. 즉, 현재 상태에서 해를 찾을 가능성이 있는지를 확인한다.
3. 가지치기(cutting off): 유망하지 않은 노드의 서브트리는 검사하지 않고 건너뛴다. 이를 통해 효율적으로 탐색을 수행한다.
4. 목표(testing): 현재 상태가 문제의 해인지를 확인한다. 해를 찾았다면 알고리즘을 종료한다.

백트래킹 예시: N-퀸 문제

 N x N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제

알고리즘 설명

1. 각 행에는 하나의 퀸만 배치할 수 있으므로, 각 행을 하나씩 확인하며 퀸을 놓을 수 있는 열을 찾는다.
2. 현재 행의 각 열에 퀸을 놓고, 유망한지를 확인한다.
3. 만약 유망하다면 다음 행으로 넘어간다. 그렇지 않다면 가지치기를 수행하고 이전 상태로 돌아간다.
4. 모든 행에 퀸을 배치하면 해를 찾은 것이므로 결과를 출력하고 종료한다.

코드:

def is_promising(board, row, col):
    # 현재 위치에 퀸을 놓을 수 있는지를 확인하는 함수
    for i in range(row):
        # 같은 열에 퀸이 있는지 확인
        if board[i] == col or abs(board[i] - col) == abs(i - row):
            return False
    return True

def n_queens(board, row, n):
    if row == n:
        # 모든 행에 퀸을 배치했을 때
        print(board)
        return

    for col in range(n):
        if is_promising(board, row, col):
            # 유망한 위치에 퀸을 배치하고 재귀적으로 다음 행 탐색
            board[row] = col
            n_queens(board, row + 1, n)

# N-퀸 문제 해결을 위한 함수 호출
n = 8  # 예시에서는 8x8 체스판을 기준으로 함
board = [0] * n  # 각 행에 놓인 퀸의 열 번호를 저장하는 리스트
n_queens(board, 0, n)

`is_promising` 함수는 현재 위치에 퀸을 놓을 수 있는지를 확인하며, `n_queens` 함수는 백트래킹을 수행한다.

이를 통해 모든 가능한 퀸의 배치를 출력한다.

 

 

 

활용 문제:

프로그래머스 LV1 - 카드 뭉치

def can_create_goal(cards1, cards2, goal):
    def backtrack(cards1, cards2, goal):
        if not goal:
            return True

        if cards1 and cards1[0] == goal[0] and backtrack(cards1[1:], cards2, goal[1:]):
            return True

        if cards2 and cards2[0] == goal[0] and backtrack(cards1, cards2[1:], goal[1:]):
            return True

        return False

    return backtrack(cards1, cards2, goal)


def solution(cards1, cards2, goal):
    answer = ''
    result = can_create_goal(cards1, cards2, goal)
    if result == True:
        answer = "Yes"
    else:
        answer = "No"

    return answer