백트래킹 (Backtracking)

백트래킹은 해결책을 찾는 과정에서 후보군을 구축하다가 해당 후보군이 해결책이 될 수 없다고 판단되면, 즉시 이전 단계로 돌아가서(백트랙) 다른 후보군을 탐색하는 문제 해결 전략이다.

알고리즘의 효율성을 높이는 중요한 기법으로, 완전 탐색보다 효율적으로 문제를 해결할 수 있게 해준다.

백트래킹은 조합 최적화 문제를 해결하는 강력한 알고리즘 패러다임이다.
모든 가능한 해결책을 체계적으로 탐색하면서도, 불가능한 경로를 조기에 차단하여 효율성을 높이는 특징이 있다.
N-Queen, 스도쿠, 미로 찾기, 조합 문제 등 다양한 영역에서 활용되며, 복잡한 문제를 해결하는 데 필수적인 도구이다.

효율적인 백트래킹 알고리즘을 작성하기 위해서는 유망함을 판단하는 조건을 잘 설계하는 것이 핵심이다.
이를 통해 최대한 많은 불필요한 탐색을 줄이고, 해결책을 빠르게 찾을 수 있다.

백트래킹의 개념

백트래킹은 가능한 모든 해결책을 탐색하는 브루트 포스(brute force) 방식을 개선한 알고리즘이다.
‘되돌아가기’라는 이름에서 알 수 있듯이, 이 방법은 해결책을 찾아가는 과정에서 더 이상 진행이 불가능하다고 판단되면 이전 단계로 돌아가(백트래킹) 다른 가능성을 시도한다.

쉽게 말해서, 백트래킹은 “일단 한 방향으로 가보고, 그 방향이 막히면 다시 돌아와서 다른 방향으로 시도하는” 전략이다.
미로를 탐색하는 사람을 상상해보자. 갈림길에서 한 방향을 선택하고, 막다른 길에 도달하면 마지막 갈림길로 돌아와 다른 방향을 시도하는 것과 같다.

특정 조건을 만족하지 않으면 더 이상 탐색하지 않고 이전 단계로 돌아가는 ‘가지치기(pruning)‘를 통해 불필요한 연산을 줄인다.

백트래킹의 핵심 개념

상태 공간 트리(State Space Tree): 문제의 모든 가능한 해결책을 나타내는 트리 구조
유망함(Promising): 현재 상태가 해결책으로 이어질 가능성이 있는지 판단하는 조건
가지치기(Pruning): 유망하지 않은 분기를 제거하여 탐색 효율을 높이는 과정

백트래킹의 동작 원리

백트래킹은 다음과 같은 단계로 작동한다:

해결책의 일부분을 구성하고 있는 현재 상태에서 시작한다.
현재 상태가 유망한지(promising) 검사한다.
유망하다면, 다음 단계로 진행한다.
유망하지 않다면, 이전 단계로 돌아가(backtrack) 다른 선택지를 탐색한다.
해결책을 찾거나 모든 가능성을 탐색할 때까지 반복한다.

Backtracking — Source: https://www.geeksforgeeks.org/introduction-to-backtracking-2/

그림에서 보여지는 것처럼,
- IS: 재귀 호출이 유효한 솔루션을 찾기 시작하는 초기 상태를 나타낸다.
- C: 재귀 호출에 대한 다른 체크포인트를 나타낸다.
- TN: 더 이상 재귀 호출을 할 수 없는 터미널 노드를 나타낸다. 이러한 노드는 재귀의 기본 사례로 작용하며 이 상태에서 현재 솔루션이 유효한지 여부를 판별한다.
각 체크포인트에서 프로그램은 몇 가지 결정을 내리고 다른 체크포인트로 이동하여 최종 노드에 도달한 후, 솔루션이 유효한지 여부를 확인한 후 프로그램은 체크포인트로 돌아가 다른 경로를 탐색하기 시작한다.
예를 들어 위의 이미지에서 TN1…TN5 는 솔루션이 허용되지 않는 최종 노드이고, TN6 은 유효한 솔루션을 찾은 상태이다.
이미지 속 뒤로 가는 화살표는 동작의 후퇴를 보여주며, 어떤 체크포인트에서 변경한 내용을 되돌리는 것을 의미한다.

백트래킹 구현 방법

백트래킹은 보통 재귀 함수를 사용하여 구현한다.
파이썬으로 구현한 일반적인 백트래킹 알고리즘의 틀은 다음과 같다:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def backtrack(candidate, depth):
    # 종료 조건 확인
    if is_solution(candidate, depth):
        # 해결책 발견
        process_solution(candidate)
        return
    
    # 다음 단계에서 가능한 선택지 탐색
    for next_candidate in get_candidates(candidate, depth):
        # 유망성 검사
        if is_promising(next_candidate, depth):
            # 선택한 후보를 해결책에 추가
            candidate.append(next_candidate)
            
            # 다음 단계 재귀 호출
            backtrack(candidate, depth + 1)
            
            # 백트래킹: 해당 후보를 제거하고 다른 후보 탐색
            candidate.pop()

백트래킹이 효과적인 문제 유형

백트래킹은 다음과 같은 문제 유형에 특히 효과적이다:

조합 문제: 특정 조건을 만족하는 조합이나 순열을 찾는 문제
제약 만족 문제: 여러 제약 조건을 만족하는 해를 찾는 문제 (스도쿠, N-Queens 등)
결정 문제: 특정 조건을 만족하는 해가 존재하는지 판단하는 문제
최적화 문제: 여러 가능한 해 중에서 최적의 해를 찾는 문제 (단, 가지치기가 효과적일 때)

백트래킹 최적화 기법

백트래킹 알고리즘의 성능을 향상시키기 위한 몇 가지 기법이 있다:

가지치기(Pruning): 유망하지 않은 경로를 일찍 제거하여 탐색 공간을 줄인다.
순서 최적화: 가장 제약이 많은 변수나 값부터 시도하여 실패 가능성이 높은 경로를 먼저 탐색한다.
메모이제이션(Memoization): 이미 계산한 부분 문제의 결과를 저장하여 재계산을 방지한다.
선 제약 검사(Forward Checking): 변수에 값을 할당할 때마다 관련된 다른 변수의 도메인을 업데이트한다.

실제 문제에 백트래킹 적용하기

백트래킹을 실제 문제에 적용하는 방법은 다음과 같다:

문제 분석: 문제의 상태 공간과 제약 조건을 명확히 이해한다.
상태 표현 정의: 문제의 상태를 어떻게 표현할지 결정한다.
유효성 검사 함수 개발: 특정 상태가 문제의 제약 조건을 만족하는지 확인하는 함수를 작성한다.
종료 조건 정의: 완전한 해를 찾았거나 더 이상 탐색할 필요가 없는 조건을 정의한다.
백트래킹 함수 구현: 상태 공간을 재귀적으로 탐색하는 백트래킹 함수를 구현한다.

개발자가 알아야 할 백트래킹 팁

종료 조건 명확화: 재귀 함수의 종료 조건을 명확히 정의하여 무한 재귀를 방지한다.
상태 관리: 백트래킹 시 상태를 올바르게 복원하여 다른 경로에 영향을 주지 않도록 한다.
가지치기 최적화: 가능한 한 일찍 유망하지 않은 경로를 제거하여 효율성을 높인다.
디버깅 전략: 각 재귀 호출의 상태를 시각화하거나 로깅하여 디버깅을 용이하게 한다.
테스트 케이스 작성: 작은 입력부터 시작하여 알고리즘의 정확성을 검증한다.

백트래킹의 장단점

장점

모든 가능한 해결책을 찾을 수 있다.
가지치기를 통해 불필요한 연산을 줄인다.
공간 효율성이 좋다(깊이에 비례한 메모리만 사용).

단점

최악의 경우 지수 시간 복잡도를 가질 수 있다.
구현이 복잡할 수 있다.
문제의 크기가 커지면 실행 시간이 급격히 증가할 수 있다.

백트래킹의 시간 복잡도

백트래킹의 시간 복잡도는 문제마다 다르지만, 일반적으로 O(b^d)로 표현된다:

b: 각 단계에서 가능한 선택지의 수(분기 계수)
d: 해결책을 찾기 위한 최대 깊이

백트래킹은 가지치기를 통해 탐색 공간을 줄이지만, 최악의 경우 모든 경우를 탐색해야 할 수도 있다. 하지만 실제로는 많은 가지를 제거하기 때문에 완전 탐색보다 훨씬 효율적이다.

백트래킹 대표 응용 사례

N-Queen 문제

N x N 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def solve_n_queens(n):
    def is_safe(board, row, col):
        # 같은 열에 퀸이 있는지 확인
        for i in range(row):
            if board[i] == col:
                return False
            
            # 대각선 위치에 퀸이 있는지 확인
            if abs(board[i] - col) == abs(i - row):
                return False
        
        return True
    
    def backtrack(board, row):
        # 모든 퀸을 배치했으면 해결책 추가
        if row == n:
            solutions.append(board[:])
            return
        
        # 현재 행의 각 열에 퀸 배치 시도
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col  # 퀸 배치
                backtrack(board, row + 1)  # 다음 행으로 진행
                # 백트래킹 (명시적으로 할 필요는 없지만 개념상 이 위치)
        
    solutions = []
    backtrack([-1] * n, 0)
    return solutions

스도쿠 풀이

9x9 격자에 1~9까지의 숫자를 중복 없이 배치하는 문제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def solve_sudoku(board):
    def is_valid(row, col, num):
        # 같은 행에 중복 체크
        for x in range(9):
            if board[row][x] == num:
                return False
        
        # 같은 열에 중복 체크
        for x in range(9):
            if board[x][col] == num:
                return False
        
        # 3x3 박스 내 중복 체크
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(3):
            for j in range(3):
                if board[box_row + i][box_col + j] == num:
                    return False
        
        return True
    
    def backtrack():
        # 빈 칸 찾기
        for row in range(9):
            for col in range(9):
                if board[row][col] == 0:  # 빈 칸
                    # 가능한 숫자 시도 (1~9)
                    for num in range(1, 10):
                        if is_valid(row, col, num):
                            board[row][col] = num  # 숫자 배치
                            
                            # 재귀적으로 다음 빈 칸 해결 시도
                            if backtrack():
                                return True
                            
                            # 실패하면 백트래킹
                            board[row][col] = 0
                    
                    # 모든 숫자가 유효하지 않음
                    return False
        
        # 모든 빈 칸이 채워짐
        return True
    
    backtrack()
    return board

부분집합의 합 문제 (Subset Sum)

주어진 집합에서 특정 합을 만드는 부분집합을 찾는 문제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def subset_sum(nums, target):
    def backtrack(start, current_sum, path):
        # 목표 합을 찾았을 때
        if current_sum == target:
            result.append(path[:])
            return
        
        # 목표 합을 초과하거나 모든 요소를 확인했을 때
        if current_sum > target or start >= len(nums):
            return
        
        # 현재 요소를 포함하는 경우
        path.append(nums[start])
        backtrack(start + 1, current_sum + nums[start], path)
        
        # 백트래킹: 현재 요소를 제외하는 경우
        path.pop()
        backtrack(start + 1, current_sum, path)
    
    result = []
    backtrack(0, 0, [])
    return result

참고 및 출처

Back Tracking vs. Brute Force

Back Tracking vs. Brute Force 브루트 포스와 백트래킹은 모두 조합 최적화 문제를 해결하는 데 사용되는 중요한 알고리즘 패러다임이다. 브루트 포스는 구현이 단순하고 모든 가능성을 확인하지만, 문제 크기가 커질수록 비효율적이다. 반면, 백트래킹은 유망성 테스트와 가지치기를 통해 불필요한 탐색을 줄여 효율성을 높이지만, 구현이 더 복잡하다. 브루트 포스(Brute Force) 브루트 포스는 가능한 모든 경우의 수를 전부 확인하는 완전 탐색 알고리즘이다. 이 방법은 문제 해결을 위해 가능한 모든 후보해를 체계적으로 나열하고 각각을 검사한다. 브루트 포스의 작동 방식: ...

Back Tracking vs. Traversal

Back Tracking vs. Traversal 백트래킹과 트래버설은 컴퓨터 과학에서 문제 해결과 데이터 구조 탐색에 사용되는 중요한 알고리즘 패러다임이다. 두 기법은 겉보기에 유사한 점이 있지만, 목적, 동작 방식, 응용 분야에서 중요한 차이점을 가지고 있다. 백트래킹과 트래버설은 서로 다른 목적과 접근 방식을 가지고 있지만, 많은 복잡한 문제 해결에서 상호 보완적으로 사용된다. 트래버설은 데이터 구조의 모든 요소를 효율적으로 방문하는 체계적인 방법을 제공하고, 백트래킹은 방대한 해결책 공간에서 효율적으로 유망한 해결책을 찾는 전략을 제공한다. 실제 문제 해결에서는 두 개념의 장점을 결합하여 사용하는 것이 효과적이다. 예를 들어, 그래프에서 특정 조건을 만족하는 경로를 찾기 위해 DFS나 BFS와 같은 트래버설 알고리즘으로 그래프를 탐색하면서, 백트래킹 기법을 활용하여 유망하지 않은 경로는 조기에 포기하는 방식이다. ...

Back Tracking vs. Depth-First Search

Back Tracking vs. Depth-First Search 백트래킹과 깊이 우선 탐색은 모두 그래프나 트리 구조에서 해결책을 찾기 위한 알고리즘 기법이다. DFS는 그래프의 모든 노드를 방문하는 데 중점을 두는 반면, 백트래킹은 제약 조건을 만족하는 해결책을 효율적으로 찾는 데 초점을 맞춘다. 백트래킹은 DFS의 개념을 기반으로 하지만, 유망성 테스트와 가지치기라는 중요한 최적화 기법을 추가하여 탐색 공간을 줄이고 효율성을 높인다. 따라서 백트래킹은 DFS의 확장된 형태라고 볼 수 있다. 깊이 우선 탐색(Depth-First Search, DFS) 깊이 우선 탐색은 그래프 탐색 알고리즘으로, 가능한 한 깊이 들어가면서 모든 노드를 방문하는 방법이다. ...