알고리즘 - 7. 깊이 우선 탐색(DFS)
깊이 우선 탐색(DFS)을 사용해야 할 때
DFS는 모든 경로를 탐색하거나 백트래킹 전에 깊이 들어가야 할 때 사용합니다. 주로 트리 순회에 사용되지만 다음과 같은 경우에도 적용할 수 있습니다:
- 트리 순회 (클래식 사용 사례 - 중위, 전위, 후위)
- 경로 찾기 (노드 간 경로 존재 확인)
- 연결된 구성요소 (그리드에서 섬 찾기)
- 사이클 감지 (그래프에서 루프 감지)
- 위상 정렬 (의존성 순서 정하기)
- 백트래킹 문제 (순열 생성, 퍼즐 해결)
- 백트래킹 전에 각 브랜치를 가능한 한 깊게 탐색해야 하는 모든 문제
예제 문제
파일 시스템 탐색: 폴더 구조가 주어졌을 때, 특정 확장자를 가진 모든 파일을 찾으세요. 파일 시스템은 다음과 같습니다:
root/
├── documents/
│ ├── report.pdf
│ └── notes.txt
├── code/
│ ├── main.js
│ └── utils/
│ └── helper.js
└── images/
└── logo.png시스템의 모든 .js 파일을 찾으세요.
답: DFS는 root → documents → report.pdf → notes.txt (백트래킹) → code → main.js (발견!) → utils → helper.js (발견!) (백트래킹) → images → logo.png을 탐색합니다. 결과: [main.js, helper.js]
가장 중요한 통찰력
DFS는 다른 경로를 시도하기 전에 하나의 경로를 완전히 탐색하는 데 전념합니다 - 각 브랜치를 재귀적으로 깊게 들어가 막다른 길에 도달한 후 백트래킹하여 대안을 탐색함으로써, 어떤 경로도 놓치지 않고 모든 노드를 정확히 한 번씩 체계적으로 방문합니다.
멘탈 노트: 이 알고리즘의 천재성은 콜 스택을 자연스러운 백트래킹 메커니즘으로 사용하는 데 있습니다. 각 노드에서 단순히 "나 자신을 처리한 다음 내 자식들을 완전히 탐색한다"고 말하면 됩니다. 재귀는 막다른 길에 도달했을 때 탐색하지 않은 브랜치로 돌아가는 것을 자동으로 처리합니다.
의사 결정 프레임워크
모든 노드에서 이 간단한 순서를 따릅니다:
- 현재 노드 처리 (언제 어떻게 처리할지는 순회 타입에 따라 다름)
- 자식들을 재귀적으로 탐색 (트리의 경우 왼쪽/오른쪽, 그래프의 경우 이웃)
- 재귀가 백트래킹을 처리하게 함 (콜 스택을 통해 자동)
유일한 결정은 현재 노드를 언제 처리할 것인가입니다:
- 전위: 자식을 탐색하기 전에 처리 (루트 → 왼쪽 → 오른쪽)
- 중위: 자식들 사이에서 처리 (왼쪽 → 루트 → 오른쪽)
- 후위: 자식을 탐색한 후에 처리 (왼쪽 → 오른쪽 → 루트)
각 순회 타입을 사용해야 할 때 (간단한 예제)
전위 순회 (루트 → 왼쪽 → 오른쪽)
필요한 경우: 자식을 처리하기 전에 부모 노드를 처리하거나 방문해야 할 때 - 일반적으로 복사본을 만들거나, 계층 구조를 출력하거나, 부모가 자식에게 필요한 정보를 포함하고 있을 때입니다.
간단한 예제: 폴더 구조 복사하기 - 폴더를 새 위치로 복사할 때 다음이 필요합니다:
- 먼저 부모 폴더를 생성 (루트)
- 그 다음 하위 폴더와 파일을 복사/생성 (자식들)
아직 존재하지 않는 폴더에 파일을 넣을 수는 없습니다!
중위 순회 (왼쪽 → 루트 → 오른쪽)
필요한 경우: 이진 검색 트리에서 정렬된 순서로 데이터를 검색해야 하거나, 노드를 자연스러운 순서대로 처리해야 할 때 - 왼쪽 서브트리에는 더 작은 값이 있고, 오른쪽 서브트리에는 더 큰 값이 있습니다.
간단한 예제: 회사 트리에서 급여별로 모든 직원 출력하기:
- 왼쪽 브랜치 = 더 낮은 급여를 받는 직원들
- 현재 노드 = 이 직원의 급여
- 오른쪽 브랜치 = 더 높은 급여를 받는 직원들
중위 순회를 하면: $50k, $60k, $70k, $80k... 정렬 알고리즘 없이 완벽하게 정렬됩니다!
후위 순회 (왼쪽 → 오른쪽 → 루트)
필요한 경우: 부모를 처리하기 전에 모든 자식으로부터 정보를 처리하거나 수집해야 할 때 - 일반적으로 삭제, 크기 계산, 또는 부모가 자식의 결과에 의존할 때입니다.
간단한 예제: 컴퓨터에서 전체 폴더 크기 계산하기:
- 먼저 하위 폴더 A의 모든 파일 크기 구하기 (왼쪽 자식)
- 그 다음 하위 폴더 B의 모든 파일 크기 구하기 (오른쪽 자식)
- 마지막으로 그것들을 합쳐서 부모 폴더의 전체 크기 구하기
모든 내용을 측정하기 전까지는 폴더의 전체 크기를 알 수 없습니다!
코드
폴더 구조에서 파일 찾기
실제 문제를 해결하기 위한 DFS를 구현해 봅시다: 프로젝트 폴더를 검색하여 모든 JavaScript 파일을 찾기. 이 예제는 DFS가 각 폴더 브랜치를 깊게 탐색한 후 다음으로 이동하며, 경로 스택을 사용하여 현재 위치를 추적하고 필요할 때 백트래킹하는 방법을 보여줍니다.
// 실용적인 예제: 폴더 구조에서 특정 파일 찾기
// 프로젝트에서 모든 JavaScript 파일을 검색해 봅시다
class FileNode {
constructor(name, isFolder = false) {
this.name = name;
this.isFolder = isFolder;
this.children = [];
}
addChild(child) {
this.children.push(child);
return child;
}
}
// 메인 DFS 알고리즘 - 특정 확장자를 가진 파일 찾기
function findFilesWithExtension(rootFolder, extension) {
const foundFiles = [];
const pathStack = []; // 전체 파일 경로를 위한 현재 경로 추적
function searchFolder(node) {
// 베이스 케이스: null이면 탐색할 것이 없음
if (node == null) {
return;
}
// 현재 항목을 경로에 추가
pathStack.push(node.name);
const currentPath = pathStack.join('/');
// DECISION FRAMEWORK: 이것이 우리가 찾는 것인지 확인
const isTargetFile = !node.isFolder && node.name.endsWith(extension);
if (isTargetFile) {
foundFiles.push(currentPath);
}
// 모든 자식을 재귀적으로 탐색 (깊게 들어가기!)
for (const child of node.children) {
searchFolder(child); // 이 자식을 완전히 탐색
}
// 백트래킹: 탐색이 끝나면 경로에서 현재 항목 제거
pathStack.pop();
}
searchFolder(rootFolder);
return foundFiles;
}
// 예제 파일 시스템 구축
const root = new FileNode('project', true);
// JavaScript 파일이 있는 src 폴더 추가
const src = root.addChild(new FileNode('src', true));
src.addChild(new FileNode('index.js'));
src.addChild(new FileNode('app.js'));
const components = src.addChild(new FileNode('components', true));
components.addChild(new FileNode('Button.js'));
components.addChild(new FileNode('Button.css')); // JS 파일이 아님
// 마크다운 파일이 있는 docs 폴더 추가
const docs = root.addChild(new FileNode('docs', true));
docs.addChild(new FileNode('README.md'));
docs.addChild(new FileNode('guide.md'));
// 루트에 설정 파일 추가
root.addChild(new FileNode('package.json'));
root.addChild(new FileNode('config.js'));
// 모든 JavaScript 파일 찾기
const jsFiles = findFilesWithExtension(root, '.js');
console.log('JavaScript 파일을 찾았습니다:');
console.log(jsFiles);
// 출력:
// [
// 'project/src/index.js',
// 'project/src/app.js',
// 'project/src/components/Button.js',
// 'project/config.js'
// ]
// DFS의 동작을 보기 위해 하나의 경로를 추적해 봅시다:
// 1. 'project'에서 시작
// 2. 첫 번째 자식 'src'로 이동 (깊게 들어가기!)
// 3. 'src'의 첫 번째 자식 'index.js'로 이동 (더 깊게!)
// 4. 'index.js'는 자식이 없으므로 처리하고 백트래킹
// 5. 'src'의 다음 자식 'app.js'로 이동 (형제 탐색)
// 6. 'app.js'는 자식이 없으므로 처리하고 백트래킹
// 7. 'src'의 다음 자식 'components'로 이동 (새 브랜치로 들어가기)
// ... 계속세 가지 순회 순서 시각화
각 순회 순서가 노드를 다르게 방문하는 방법을 보기 위해 간단한 트리를 사용해 봅시다:
A
/ \
B C
/ \
D E이 트리 구조에서 각 순회 타입은 부모를 자식에 대해 언제 처리하는지에 따라 다른 순서로 노드를 방문합니다.
class SimpleNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 전위 순회: 자식 전에 노드 처리 (루트 → 왼쪽 → 오른쪽)
function preOrder(node) {
if (node == null) return [];
const result = [];
function traverse(current) {
if (current == null) return;
// DECISION FRAMEWORK: 현재를 먼저 처리
result.push(current.value);
traverse(current.left); // 그 다음 왼쪽으로
traverse(current.right); // 그 다음 오른쪽으로
}
traverse(node);
return result;
}
// 중위 순회: 자식 사이에 노드 처리 (왼쪽 → 루트 → 오른쪽)
function inOrder(node) {
if (node == null) return [];
const result = [];
function traverse(current) {
if (current == null) return;
traverse(current.left); // 먼저 왼쪽으로
// DECISION FRAMEWORK: 현재를 중간에 처리
result.push(current.value);
traverse(current.right); // 그 다음 오른쪽으로
}
traverse(node);
return result;
}
// 후위 순회: 자식 후에 노드 처리 (왼쪽 → 오른쪽 → 루트)
function postOrder(node) {
if (node == null) return [];
const result = [];
function traverse(current) {
if (current == null) return;
traverse(current.left); // 먼저 왼쪽으로
traverse(current.right); // 그 다음 오른쪽으로
// DECISION FRAMEWORK: 현재를 마지막에 처리
result.push(current.value);
}
traverse(node);
return result;
}
// 예제 트리 구축
const tree = new SimpleNode('A');
tree.left = new SimpleNode('B');
tree.right = new SimpleNode('C');
tree.left.left = new SimpleNode('D');
tree.left.right = new SimpleNode('E');
console.log('\n순회 순서:');
console.log('전위 (루트-왼쪽-오른쪽):', preOrder(tree)); // [A, B, D, E, C]
console.log('중위 (왼쪽-루트-오른쪽):', inOrder(tree)); // [D, B, E, A, C]
console.log('후위 (왼쪽-오른쪽-루트):', postOrder(tree)); // [D, E, B, C, A]
// 각 순회의 실제 의미:
// 전위: 트리의 복사본 만들기 (자식 전에 부모 처리)
// 중위: BST에서 정렬된 값 얻기 (왼쪽 < 루트 < 오른쪽)
// 후위: 트리를 안전하게 삭제 (부모 전에 자식 삭제)의심 버스터
일반적인 의심: "DFS가 무한 루프에 빠지거나 노드를 다시 방문하지 않을까요? 사이클이 있는 그래프가 있거나 트리가 실제로 거대하다면 메모리가 부족하지 않을까요?"
왜 DFS가 실패할 수 있다고 생각할 수 있는가
사람들이 서로 친구가 될 수 있는 (사이클을 만드는) 소셜 네트워크 탐색을 고려해보세요:
Alice → Bob → Charlie
↑ ↓
└─────────────┘다음과 같이 걱정할 수 있습니다:
- "Alice에서 시작해서 Bob으로 가고, Charlie로 가고, 다시 Alice로 돌아오면... 영원히 갇혀버린다!"
- "트리가 1000 레벨 깊이라면? 콜 스택이 오버플로우되지 않을까?"
- "같은 노드를 여러 번 처리하지 않는다는 것을 어떻게 알 수 있을까?"
왜 이런 생각이 불완전한가
핵심 깨달음: DFS는 이러한 우려에 대한 두 가지 간단한 해결책을 가지고 있습니다:
- 사이클 처리: 방문한 노드를 추적하기 위해 방문 세트 사용
- 깊이 처리: 콜 스택 공간은 O(높이)이지 O(노드)가 아님
사이클이 있는 그래프를 어떻게 처리하는지 봅시다:
function dfsGraph(startNode, graph) {
const visited = new Set();
const result = [];
function explore(node) {
// 재방문 방지 - 이것이 사이클을 끊는다!
if (visited.has(node)) {
return;
}
visited.add(node);
result.push(node);
// 방문하지 않은 모든 이웃 탐색
for (const neighbor of graph[node]) {
explore(neighbor);
}
}
explore(startNode);
return result;
}
// 사이클이 있는 그래프 예제
const socialNetwork = {
'Alice': ['Bob', 'Charlie'],
'Bob': ['Charlie'],
'Charlie': ['Alice'] // 사이클 생성!
};
console.log(dfsGraph('Alice', socialNetwork));
// ['Alice', 'Bob', 'Charlie'] - 무한 루프 없음!구체적인 예제: DFS는 모든 트리 모양을 효율적으로 처리
DFS가 견고한 이유를 보기 위해 다양한 트리 모양을 추적해 봅시다:
극도로 깊은 트리 (링크드 리스트 모양):
1 → 2 → 3 → 4 → ... → 1000- 공간 복잡도: 콜 스택을 위한 O(1000)
- 하지만 여전히 1000개의 노드를 모두 정확히 한 번씩 방문
- 현대 시스템은 수천 개의 재귀 호출을 쉽게 처리
극도로 넓은 트리:
1
/ / | \ \
2 3 4 5 6 (1000개의 자식)- 공간 복잡도: O(2) - 현재 경로 깊이만!
- 자식 2를 완전히 탐색하고 백트래킹한 후 자식 3 등
- 모든 형제를 동시에 저장할 필요 없음
균형 잡힌 트리:
1
/ \
2 3
/ \ / \
4 5 6 7- 균형 잡힌 트리의 공간 복잡도: O(log n)
- 재귀적 탐색을 위한 가장 효율적인 경우
왜 O(log n)인가? n개의 노드를 가진 균형 잡힌 트리에서 높이는 log₂(n)입니다. 예를 들어, 1,000,000개의 노드를 가진 균형 잡힌 트리의 높이는 약 20 레벨밖에 되지 않습니다. DFS는 현재 경로만 메모리에 유지하므로(모든 노드가 아님), 백만 개의 노드가 있어도 콜 스택은 20 프레임을 초과하지 않습니다!
수학적 증명: 공간 복잡도가 O(log n)인 이유
균형 잡힌 이진 트리에서 n개의 노드가 높이 log₂(n)을 갖는 이유를 단계별로 증명해보겠습니다:
1단계: 균형 잡힌 이진 트리의 구조 이해
- 각 레벨 i는 최대 2^i개의 노드를 가집니다 (레벨 0은 1개, 레벨 1은 2개, 레벨 2는 4개 등)
- 높이 h의 완전 균형 트리는 정확히 2^(h+1) - 1개의 노드를 가집니다
2단계: 노드 수(n)와 높이(h)의 관계 도출
높이 h의 균형 잡힌 트리:
- 최대 노드 = 1 + 2 + 4 + 8 + ... + 2^h
- 이것은 기하급수 = 2^(h+1) - 1
따라서: n ≤ 2^(h+1) - 1왜 n ≤ 2^(h+1) - 1인가? 이 부등식은 높이 h인 이진 트리의 최대 노드 수를 나타냅니다:
- 각 레벨 i는 최대 2^i개의 노드를 가질 수 있음
- 총 노드 = 2^0 + 2^1 + 2^2 + ... + 2^h (모든 레벨의 합)
- 기하급수 공식 사용: 합 = a(r^n - 1)/(r - 1), 여기서 a=1, r=2, n=h+1
- 결과: n = (2^(h+1) - 1)/1 = 2^(h+1) - 1
= (등호)가 아닌 ≤ (부등호)를 사용하는 이유는 트리가 마지막 레벨에서 완전히 채워지지 않을 수 있기 때문입니다. 예를 들어, 다음 두 높이 2인 트리 모두 유효합니다:
완전한 트리 (n = 7): 불완전한 트리 (n = 4):
1 1
/ \ / \
2 3 2 3
/ \ / \ /
4 5 6 7 4도출 계속:
n + 1 ≤ 2^(h+1)
log₂(n + 1) ≤ h + 1
h ≥ log₂(n + 1) - 1
h는 최소한 log₂(n)이어야 하므로, h = O(log n)3단계: 실제 숫자로 보는 구체적인 예시
7개 노드의 트리 (완전 균형):
1 높이 = 2
/ \ 각 레벨의 노드:
2 3 레벨 0: 1개 노드
/| |\ 레벨 1: 2개 노드
4 5 6 7 레벨 2: 4개 노드
총: 7개 노드 = 2^3 - 1
높이: 2 = floor(log₂(7)) ✓
1,000,000개 노드의 트리:
log₂(1,000,000) ≈ 19.93
높이 ≈ 20 레벨
1,000,000,000개 노드의 트리 (10억):
log₂(1,000,000,000) ≈ 29.9
높이 ≈ 30 레벨4단계: DFS 공간 복잡도에 미치는 영향
DFS는 루트에서 현재 노드까지의 현재 경로만 콜 스택에 저장합니다:
DFS 순회 중 콜 스택:
[root] → 1 프레임 (루트에서)
[root, left] → 2 프레임 (왼쪽 자식에서)
[root, left, left.left] → 3 프레임 (left.left 자식에서)
...
[root, ..., leaf] → h+1 프레임 (가장 깊은 리프에서)
최대 스택 프레임 = 높이 + 1 = 균형 트리의 경우 O(log n)노드 수 vs 높이의 시각적 비교:
노드 수 (n) | 높이 (h) | 필요한 스택 프레임
------------- | -------- | -----------------
7 | 2 | 3
15 | 3 | 4
31 | 4 | 5
1,023 | 9 | 10
1,048,575 | 19 | 20
1,073,741,823 | 29 | 3010억 개가 넘는 노드에도 불구하고 30개의 스택 프레임만 필요합니다! 이것이 로그 성장의 힘입니다 - 높이는 노드 수보다 훨씬 천천히 증가합니다.
왜 콜 스택이 우리의 친구인가
DFS의 뛰어난 점은 콜 스택이 자동으로 다음을 제공한다는 것입니다:
- 돌아갈 위치의 메모리 - 브랜치 탐색을 마치면 스택은 정확히 어디서 중단했는지 압니다
- 암시적 백트래킹 - "어디로 돌아갈지" 수동으로 추적할 필요 없음
- 자연스러운 깊이 제한 - 스택 오버플로우는 실제로 무한 재귀를 방지하는 기능입니다
각 재귀 호출은 스택에 하나의 프레임만 추가합니다:
explore(root) // 스택: [root]
explore(left) // 스택: [root, left]
explore(left.left) // 스택: [root, left, left.left]
return // 스택: [root, left] - 자동 백트래킹!
explore(left.right) // 스택: [root, left, left.right]
return // 스택: [root, left]
return // 스택: [root]
explore(right) // 스택: [root, right]보장: 모든 노드는 정확히 한 번 방문되며, 사용되는 최대 메모리는 트리의 전체 크기가 아닌 높이에 비례합니다. 그래프의 경우, 방문 세트는 노드를 두 번 처리하지 않도록 보장하여 무한 루프를 완전히 제거합니다.