Backtracking(백트래킹)과 DFS의 차이점

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

DFS는 그래프 탐색 알고리즘 중 하나로, 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식입니다.

• 보통 재귀(Recursion)나 스택(Stack) 을 사용하여 구현합니다.
• 그래프 탐색에서 특정 노드를 방문한 후, 그 자식 노드들을 방문하는 방식입니다.
• DFS는 모든 가능한 경우를 무조건 탐색하는 경우가 많습니다.

예시: 그래프에서 DFS 탐색

graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [],
    6: []
}

visited = set()

def dfs(node):
    if node in visited:
        return
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        dfs(neighbor)

dfs(1)  # 출력: 1 2 4 5 3 6

 

 

2. Backtracking (백트래킹)

백트래킹은 DFS를 기반으로 불필요한 탐색을 가지치기(pruning)하여 최적화하는 기법입니다.

• 모든 경우를 탐색하는 것이 아니라, 가능성이 없는 경로는 빨리 포기(가지치기) 합니다.
• 해가 될 가능성이 없는 경우, 재귀 호출을 중단하여 불필요한 계산을 줄입니다.
• 주로 조합(combination), 순열(permutation), 부분집합(subset) 문제에서 사용됩니다.

백트래킹 예시 (순열)

아래 코드는 DFS를 사용하여 모든 순열을 탐색하지만, 이미 선택한 숫자는 다시 선택하지 않도록 하여 가지치기를 합니다.

 

def permute(nums):
    res, item = [], []
    
    def dfs():
        if len(item) == len(nums):
            res.append(item[:])  # 정답 리스트에 추가
            return
        
        for num in nums:
            if num not in item:  # 이미 선택한 숫자는 다시 선택하지 않음 (가지치기)
                item.append(num)
                dfs()
                item.pop()  # 백트래킹: 원상복구
        
    dfs()
    return res

print(permute([1, 2, 3]))
# 출력: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

 

결론: DFS vs Backtracking

개념설명특징

DFS (깊이 우선 탐색)	모든 경로를 탐색하는 방식	그래프 탐색, 트리 탐색 등에 사용됨
Backtracking (백트래킹)	DFS 기반이지만, 불가능한 경로는 가지치기	조합, 순열, N-Queen, Sudoku, 부분집합 문제에서 자주 사용됨

즉, 백트래킹은 DFS의 일종이지만, 최적화를 위해 가지치기를 추가한 기법입니다.