[TIL, 일일 회고] 2025.01.23 - DFS와 백트래킹 알고리즘의 차이점 알아보기

 

개요

알고리즘을 공부하다 보면 자주 마주치는 두 가지 개념이 있습니다.

 

바로 백트래킹(Backtracking)과 깊이 우선 탐색(DFS, Depth-First Search)인데요. 본 글에서는 얼핏 보면 비슷해 보이는 이 두 알고리즘의 차이점에 대해 정리하고자 합니다.

 

 

깊이 우선 탐색(DFS)이란❓

DFS는 그래프나 트리를 탐색하는 방법 중 하나입니다.

 

시작 정점에서 출발하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 마치 미로를 탐색할 때 한 방향으로 끝까지 가보는 것과 같습니다.

 

[Algorithm] 효율적인 그래프 탐색: 자바로 구현한 DFS 알아보기 (1/2)

 

 

백트래킹이란❓

백트래킹은 해를 찾아가는 도중, 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법입니다.

 

일반적으로 문제를 풀 때 선택할 수 있는 모든 경우를 전부 확인하는 것이 아니라, 처음부터 해가 될 수 없는 경우를 제외하고 탐색하는 방법입니다.

[Algorithm] 백트래킹(Backtracking) 알고리즘 알아보기

 

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

1. 목적의 차이

 

• DFS: 모든 노드를 탐색하는 것이 목적입니다.
• 백트래킹: 해를 찾는 것이 목적이며, 불필요한 탐색을 하지 않습니다.

 

2. 가지치기(Pruning)의 유무

 

• DFS: 모든 경로를 탐색합니다.
• 백트래킹: 유망하지 않은 경로는 더 이상 탐색하지 않고 가지치기를 합니다.

 

3. 효율성

 

• DFS: 모든 경우를 탐색하므로 백트래킹에 비해 비효율적일 수 있습니다.
• 백트래킹: 불필요한 탐색을 하지 않으므로 일반적으로 더 효율적입니다.

 

예시 : N 과 M(1)

백준 15649번 "N과 M (1)" 문제를 통해 백트래킹과 DFS의 실제 구현 차이를 살펴보겠습니다.

 

해당 문제는 자연수 N과 M이 주어졌을 때, 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 모두 출력하는 문제입니다.

[백준, 15649번] N과 M(1) (백트래킹, Java)

자세한 풀이와 설명은 위 포스팅에서 확인 가능합니다.

---

DFS 핵심 코드

// 현재 숫자가 이미 수열에 있는지 매번 확인
boolean isUsed = false;
for(int j = 0; j < depth; j++) {
    if(sequence[j] == i) {
        isUsed = true;
        break;
    }
}
if(!isUsed) {
    sequence[depth] = i;
    dfs(N, M, depth + 1);
}

 

백트래킹 핵심 코드

if(!visited[i]) {
    visited[i] = true;     // 상태 변경
    arr[count] = i;
    getPermutation(N, M, count + 1, arr);
    visited[i] = false;    // 상태 복구(백트래킹)
}

 

1. DFS는 현재 수열을 매번 처음부터 끝까지 순회하며 중복을 확인합니다.
   • 반면 백트래킹은 visited 배열을 사용해 O(1) 시간에 중복 여부를 즉시 확인할 수 있습니다.
2. 백트래킹은 상태 관리가 핵심입니다.
   • 노드 방문 시 visited[i] = true로 상태를 변경하고, 해당 경로의 탐색이 끝나면 visited[i] = false로 상태를 되돌립니다.
   • 이에 비해 DFS는 별도의 상태 관리 없이 단순 탐색을 수행합니다.
3. 시간 복잡도 측면에서 백트래킹이 더 효율적입니다.
   • DFS는 매 단계에서 중복 검사를 위해 O(M) 시간이 필요하지만, 백트래킹은 O(1) 시간에 검사가 가능합니다.