Back Tracking vs. Depth-First Search

백트래킹과 깊이 우선 탐색은 모두 그래프나 트리 구조에서 해결책을 찾기 위한 알고리즘 기법이다.

DFS는 그래프의 모든 노드를 방문하는 데 중점을 두는 반면, 백트래킹은 제약 조건을 만족하는 해결책을 효율적으로 찾는 데 초점을 맞춘다.

백트래킹은 DFS의 개념을 기반으로 하지만, 유망성 테스트와 가지치기라는 중요한 최적화 기법을 추가하여 탐색 공간을 줄이고 효율성을 높인다. 따라서 백트래킹은 DFS의 확장된 형태라고 볼 수 있다.

깊이 우선 탐색(Depth-First Search, DFS)

깊이 우선 탐색은 그래프 탐색 알고리즘으로, 가능한 한 깊이 들어가면서 모든 노드를 방문하는 방법이다.

DFS의 작동 방식:

시작 노드를 스택에 넣고 ‘방문 완료’로 표시한다.
스택이 비어있지 않은 동안 다음을 반복한다:
- 스택의 최상위 노드를 꺼낸다.
- 해당 노드의 모든 인접 노드 중 방문하지 않은 노드를 스택에 넣고 ‘방문 완료’로 표시한다.
스택이 비면 탐색이 종료된다.

DFS의 특징

완전 탐색: 연결된 모든 노드를 방문한다.
메모리 효율성: 현재 경로 상의 노드만 기억하므로 메모리 사용이 효율적이다.
재귀적 구현: 주로 재귀 함수로 구현되지만, 명시적인 스택을 사용할 수도 있다.
경로 발견: 시작 노드에서 임의의 노드까지의 경로를 찾는 데 유용하다.
사이클 감지: 그래프에서 사이클을 찾는 데 사용될 수 있다.

DFS 예제: 그래프 탐색

 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
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    # 현재 노드를 방문 표시
    visited.add(start)
    print(f"방문: {start}")
    
    # 인접 노드 탐색
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    
    return visited

# 예시 그래프 (인접 리스트 형태)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# DFS 수행
dfs(graph, 'A')

백트래킹(Backtracking)

백트래킹은 해결책을 찾는 과정에서 더 이상 유망하지 않은 경로를 만나면 즉시 이전 단계로 돌아가(백트랙) 다른 경로를 탐색하는 알고리즘이다.

백트래킹의 작동 방식:

해결책의 후보를 단계별로 구성한다.
각 단계에서 현재 후보가 유망한지(promising) 검사한다.
유망하지 않다면 즉시 탐색을 중단하고 이전 단계로 돌아간다(가지치기).
유망하다면 다음 단계로 진행한다.
해결책을 찾거나 모든 가능성을 탐색할 때까지 이 과정을 반복한다.

백트래킹의 특징

가지치기: 유망하지 않은 경로는 탐색하지 않고 가지치기를 통해 탐색 공간을 줄인다.
유망성 테스트: 현재 경로가 해결책으로 이어질 가능성이 있는지 평가한다.
재귀적 구현: 대부분 재귀 함수로 구현된다.
최적화: 불필요한 탐색을 줄여 효율성을 높인다.
제약 충족 문제: 제약 조건이 있는 문제 해결에 적합하다.

백트래킹 예제: N-Queens 문제

 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):
    board = [-1] * n  # board[i]는 i번째 행에서 퀸의 열 위치
    solutions = []
    
    def is_promising(row):
        for i in range(row):
            # 같은 열에 있거나 대각선 상에 있는지 확인
            if board[i] == board[row] or abs(board[i] - board[row]) == row - i:
                return False
        return True
    
    def place_queen(row):
        if row == n:  # 모든 퀸을 성공적으로 배치했을 때
            solutions.append(board[:])
            return
        
        for col in range(n):
            board[row] = col  # row번째 행의 col번째 열에 퀸 배치
            
            # 유망성 테스트: 현재 배치가 유망한 경우에만 다음 행으로 진행
            if is_promising(row):
                place_queen(row + 1)
    
    place_queen(0)
    return solutions

# 8-Queens 문제 해결
solutions = solve_n_queens(8)
print(f"해결책 수: {len(solutions)}")

DFS와 백트래킹의 주요 차이점

목적과 사용 사례
- DFS: 그래프의 모든 노드를 방문하거나, 특정 노드를 찾는 등 그래프 탐색이 주목적.
- 백트래킹: 제약 조건을 만족하는 해결책을 찾는 것이 주목적으로, 조합 최적화 문제나 결정 문제 해결에 사용된다.
가지치기(Pruning)
- DFS: 기본적인 DFS는 가지치기를 수행하지 않고 모든 경로를 탐색한다.
- 백트래킹: 유망성 테스트를 통해 유망하지 않은 경로는 탐색하지 않는 가지치기가 핵심.
효율성
- DFS: 모든 노드를 방문하므로 탐색 공간이 크면 비효율적일 수 있다.
- 백트래킹: 가지치기를 통해 탐색 공간을 줄여 DFS보다 효율적.
문제 해결 접근 방식
- DFS: 주로 그래프 관련 문제(경로 찾기, 연결 요소 찾기 등)에 사용.
- 백트래킹: 제약 충족 문제(스도쿠, N-Queens 등)나 조합 최적화 문제에 사용.
구현 차이
- DFS: 방문 여부를 추적하는 데 중점을 둔다.
- 백트래킹: 유망성 테스트와 상태 관리에 중점을 둔다.

실제 적용 사례 비교

미로 탐색 문제
1. DFS 접근법
  - 미로의 각 지점을 노드로, 이동 가능한 경로를 간선으로 표현.
  - 시작점에서 출발하여 모든 가능한 경로를 깊이 우선으로 탐색.
  - 이미 방문한 지점은 다시 방문하지 않는다.
  - 목적지에 도달하면 성공, 모든 경로를 탐색해도 도달하지 못하면 실패.
2. 백트래킹 접근법
  - DFS와 유사하게 시작하지만, 특정 경로가 유망하지 않다고 판단되면 즉시 탐색을 중단.
  - 예를 들어, 현재까지의 이동 거리가 이미 알려진 최단 경로보다 길다면 해당 경로는 더 이상 탐색하지 않는다.
  - 또는 현재 위치에서 목적지까지의 맨해튼 거리가 남은 이동 횟수보다 크다면 해당 경로는 탐색하지 않는다.
단어 검색 퍼즐(Word Search Puzzle)
1. DFS 접근법
  - 격자의 각 셀에서 시작하여 상, 하, 좌, 우, 대각선 방향으로 DFS를 수행.
  - 이미 방문한 셀은 다시 방문하지 않는다.
  - 목표 단어를 찾으면 성공, 모든 가능한 경로를 탐색해도 찾지 못하면 실패.
2. 백트래킹 접근법
  - DFS와 비슷하게 시작하지만, 현재까지 형성된 문자열이 목표 단어의 접두사가 아니라면 즉시 탐색을 중단.
  - 예를 들어, “APPLE"을 찾는 중에 “APZ"가 형성되면, 이는 “APPLE"의 접두사가 아니므로 해당 경로는 더 이상 탐색하지 않는다.

DFS와 백트래킹이 모두 사용되는 사례

일부 문제는 DFS와 백트래킹을 모두 활용하여 해결할 수 있다.

예를 들어:

순열/조합 생성

 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
def generate_permutations(elements):
    n = len(elements)
    result = []
    used = [False] * n
    current = []
    
    def backtrack():
        if len(current) == n:
            result.append(current[:])
            return
        
        for i in range(n):
            if used[i]:
                continue
            
            # 현재 원소 선택
            used[i] = True
            current.append(elements[i])
            
            # 다음 단계로 재귀 호출 (DFS)
            backtrack()
            
            # 백트래킹: 선택 취소
            used[i] = False
            current.pop()
    
    backtrack()
    return result

# 예시: [1, 2, 3]의 모든 순열 생성
permutations = generate_permutations([1, 2, 3])
print(permutations)

이 코드에서는 DFS를 사용하여 가능한 모든 순열을 탐색하면서, 백트래킹 기법(선택한 원소를 다시 취소하는 과정)을 함께 활용한다.

DFS와 백트래킹을 결합한 고급 알고리즘

두 알고리즘의 장점을 결합한 고급 알고리즘도 존재한다:

알파-베타 가지치기(Alpha-Beta Pruning)

미니맥스(Minimax) 알고리즘에 가지치기를 적용한 것으로, 게임 트리 탐색에 사용된다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def minimax_alpha_beta(node, depth, alpha, beta, maximizing_player):
    if depth == 0 or is_terminal_node(node):
        return evaluate(node)
    
    if maximizing_player:
        max_eval = float('-inf')
        for child in get_children(node):
            eval = minimax_alpha_beta(child, depth - 1, alpha, beta, False)
            max_eval = max(max_eval, eval)
            alpha = max(alpha, eval)
            if beta <= alpha:
                break  # 베타 컷오프 (가지치기)
        return max_eval
    else:
        min_eval = float('inf')
        for child in get_children(node):
            eval = minimax_alpha_beta(child, depth - 1, alpha, beta, True)
            min_eval = min(min_eval, eval)
            beta = min(beta, eval)
            if beta <= alpha:
                break  # 알파 컷오프 (가지치기)
        return min_eval

분기한정법(Branch And Bound)

최적화 문제를 해결하기 위한 알고리즘으로, DFS에 하한(lower bound)과 상한(upper bound)을 사용한 가지치기를 적용한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def branch_and_bound(node, best_solution):
    if is_leaf(node):
        if value(node) > value(best_solution):
            best_solution = node
        return best_solution
    
    # 하한값 계산
    lower_bound = calculate_lower_bound(node)
    
    # 가지치기: 현재 노드의 하한값이 현재 최적해보다 작으면 탐색 중단
    if lower_bound <= value(best_solution):
        return best_solution
    
    # DFS 계속 진행
    for child in get_children(node):
        best_solution = branch_and_bound(child, best_solution)
    
    return best_solution

DFS와 백트래킹의 관계

백트래킹은 DFS를 기반으로 하지만, 가지치기라는 중요한 최적화 기법이 추가된 알고리즘이다. 따라서 모든 백트래킹 알고리즘은 DFS를 사용하지만, 모든 DFS가 백트래킹인 것은 아니다.

DFS는 그래프 탐색 알고리즘이라면, 백트래킹은 문제 해결 패러다임이라고 볼 수 있다. 백트래킹은 DFS의 개념을 확장하여 유망성 테스트와 가지치기를 통해 효율성을 높인 알고리즘이다.

백트래킹과 DFS의 비교

특성	깊이 우선 탐색 (DFS)	백트래킹 (Backtracking)
정의	가능한 한 깊이 들어가면서 모든 노드를 방문하는 그래프 탐색 알고리즘	해결책을 찾는 과정에서 유망하지 않은 경로를 조기에 차단하는 알고리즘
주요 목적	그래프의 모든 노드 방문, 경로 찾기, 연결 요소 찾기	제약 조건을 만족하는 해결책 찾기, 조합 최적화 문제 해결
가지치기(Pruning) 여부	없음 (기본적으로 모든 경로 탐색)	있음 (핵심 특징)
유망성 테스트	없음 (단순히 방문 여부만 확인)	있음 (현재 경로가 해결책으로 이어질 가능성 평가)
시간 복잡도	O(V + E) (V: 노드 수, E: 간선 수)	문제에 따라 다양하지만, 가지치기로 인해 일반적으로 DFS보다 개선됨
공간 복잡도	O(V) (최악의 경우, V: 노드 수)	O(d) (d: 최대 재귀 깊이)
활용 분야	그래프 알고리즘, 위상 정렬, 사이클 감지	순열/조합 생성, 스도쿠, N-Queens, 부분집합 합 문제 등
완전성	모든 노드를 방문함	가지치기로 일부 경로를 건너뛰지만, 해결책이 있다면 항상 찾음
구현 방식	재귀 또는 명시적 스택	주로 재귀
상태 관리	방문 여부 관리	현재 상태, 선택 이력, 제약 조건 만족 여부 등 복잡한 상태 관리
최적화 기법	방문 표시를 통한 중복 방문 방지	유망성 테스트, 가지치기, 휴리스틱 활용 등 다양한 최적화
메모리 사용	모든 노드의 방문 여부 기록	현재 경로 상의 노드와 상태 정보만 기록
적합한 문제 유형	그래프 탐색 문제	제약 충족 문제, 조합 최적화 문제
알고리즘 성격	그래프 탐색 알고리즘	문제 해결 패러다임
핵심 동작	스택 또는 재귀를 사용한 깊이 우선 탐색	시도-실패-되돌아가기(try-fail-backtrack) 반복
대표적 예제	그래프 탐색, 미로 찾기	N-Queens, 스도쿠, 부분집합 합 문제
종료 조건	모든 도달 가능한 노드 방문	해결책 발견 또는 모든 가능한 경로 탐색
중간 상태의 유효성	고려하지 않음	핵심적으로 고려 (유망성 테스트)
백트래킹 시점	더 이상 방문할 노드가 없을 때	유망하지 않은 상태에 도달했을 때
해결책 표현	일반적으로 경로 또는 방문 순서	상태 공간에서의 특정 경로 또는 선택 집합

언제 어떤 방법을 사용해야 할까?

DFS를 선택해야 할 때

그래프의 모든 노드를 방문해야 할 때
그래프에서 경로를 찾거나 사이클을 감지해야 할 때
위상 정렬이 필요할 때
연결 요소를 찾아야 할 때
문제의 상태 공간이 명확한 그래프 구조를 가질 때

백트래킹을 선택해야 할 때

제약 조건을 만족하는 해결책을 찾아야 할 때
최적화 문제(예: 최소/최대값 찾기)를 해결해야 할 때
가능한 모든 조합을 생성해야 하지만, 제약 조건으로 인해 일부 조합이 불가능할 때
문제의 크기가 커서 효율적인 가지치기가 필요할 때
문제가 명확한 유망성 테스트를 정의할 수 있을 때