백엔드 개발자로서 복잡한 데이터 구조를 다루거나 코딩 테스트를 준비할 때 반드시 마주치는 거대한 벽이 있습니다. 바로 그래프 탐색 알고리즘입니다. 수많은 알고리즘 중에서도 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 모든 트리와 그래프 문제의 뿌리가 되는 핵심 중의 핵심입니다.
개념 자체는 단순해 보이지만, 실전 문제나 실무 아키텍처에서 "이 상황에는 어떤 탐색 기법을 써야 최적의 성능을 낼 수 있는가?"라는 질문에 명확한 기준을 제시하지 못하면 치명적인 타임아웃(Time Out)이나 메모리 초과 에러를 마주하게 됩니다. 이번 포스팅에서는 BFS와 DFS의 작동 원리를 시각적으로 이해하고, 실전에서 바로 써먹는 마법 같은 선택 기준을 공유합니다.
1. 두 탐색 알고리즘의 핵심 개념 및 작동 원리
그래프 탐색이란 하나의 정점(Node)으로부터 시작하여 연결된 모든 정점들을 한 번씩 방문하는 과정을 말합니다. 이 방문하는 '방향성'에 따라 두 알고리즘의 성격이 완전히 갈립니다.
🌲 DFS (Depth-First Search): 깊이 우선 탐색
DFS는 이름 그대로 "갈 수 있는 만큼 깊이 파고드는" 전략입니다. 한 경로를 선택하면 그 경로의 끝(리프 노드)에 도달할 때까지 아래로만 직진합니다. 더 이상 갈 곳이 없으면 가장 최근의 갈림길로 되돌아와서(Backtracking) 다른 경로를 탐색합니다.
- 핵심 자료구조: 미로 찾기에서 직전에 지나온 길을 기억해야 하므로 스택(Stack) 구조를 사용하며, 실무 및 코딩 테스트에서는 구현이 직관적인 재귀 함수(Recursion) 형태로 주로 구현합니다.
🗺️ BFS (Breadth-First Search): 너비 우선 탐색
BFS는 "가까운 이웃부터 차례대로 평평하게 넓혀가는" 전략입니다. 시작 정점에서 거리가 1인 모든 정점을 먼저 방문하고, 그다음 거리가 2인 정점들을 방문하는 방식입니다. 잔잔한 호수에 돌을 던졌을 때 파동이 사방으로 퍼져나가는 모습을 상상하면 쉽습니다.
- 핵심 자료구조: 먼저 발견한 정점을 먼저 방문해야 하므로 선입선출(FIFO) 방식의 큐(Queue) 구조를 강제합니다.
2. JavaScript/TypeScript 실전 코드 구현 가이드
인접 리스트 구조로 표현된 그래프를 두 가지 방식으로 탐색하는 표준 템플릿 코드입니다.
const graph: Record<number, number[]> = {
1: [2, 3],
2: [4, 5],
3: [6],
4: [],
5: [],
6: []
};
// 1. DFS 구현 (재귀 함수 방식)
function dfs(node: number, visited: Set<number> = new Set()) {
if (visited.has(node)) return;
console.log(`DFS 방문: ${node}`);
visited.add(node);
for (const neighbor of graph[node] || []) {
dfs(neighbor, visited); // 깊게 파고들기
}
}
// 2. BFS 구현 (큐 방식)
function bfs(startNode: number) {
const visited = new Set<number>();
const queue: number[] = [startNode]; // 큐 초기화
visited.add(startNode);
while (queue.length > 0) {
const node = queue.shift()!; // 앞개체 꺼내기
console.log(`BFS 방문: ${node}`);
for (const neighbor of graph[node] || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor); // 이웃들을 뒤로 추가
}
}
}
}3. 무엇을 언제 써야 할까?
실전에서 마주하는 알고리즘 문제들은 대놓고 "BFS로 푸세요"라고 말하지 않습니다. 문제의 요구사항 속에 숨겨진 힌트를 보고 도구를 선택해야 합니다.
💡 이런 문제는 무조건 'BFS'를 선택하세요
- 최단 거리, 최단 경로, 최소 횟수 구하기: 미로 찾기나 네트워크 최단 거리를 구할 때 BFS는 먼저 도착 지점에 도달하는 순간 탐색을 즉시 종료할 수 있습니다. 그 순간의 깊이가 곧 최단 거리임을 보장하기 때문입니다. (DFS는 최단 경로가 아님에도 끝까지 파고들 수 있어 부적합합니다.)
- 트래픽 레벨이 넓게 퍼져있을 때: 목표 노드가 시작 노드 근처에 있을 것이라 예상될 때 유리합니다.
💡 이런 문제는 무조건 'DFS'를 선택하세요
- 이동할 때마다 가중치가 바뀌거나 제약이 있을 때: "특정 경로로 이동할 때마다 점수를 얻고, 누적 점수가 몇 점 이상이어야 한다"와 같이 경로 자체의 특징을 유지하고 추적해야 할 때는 DFS가 압도적으로 유리합니다.
- 모든 경우의 수를 전부 조합해야 할 때 (백트래킹): 순열, 조합, 가계도 탐색 등 그래프의 모든 노드를 완벽하게 순회하며 조건을 검사해야 하는 완전 탐색 문제에 적합합니다.
- 메 메모리 관리 효율성: 그래프의 폭(Breadth)이 너무 넓고 깊이가 얕다면, BFS는 큐에 너무 많은 노드를 담아 메모리 초과를 일으킬 수 있습니다. 이때는 스택만 가볍게 유지하는 DFS가 유리합니다.
4. 결론
BFS와 DFS는 단순한 암기용 알고리즘이 아니라, 복잡한 인프라 종속성 관계를 파악하거나 SNS의 친구 추천 아키텍처를 설계할 때도 응용되는 백엔드의 유산입니다.시간 복잡도는 두 방식 모두 모든 정점(V)과 간선(E)을 확인하므로 O(V + E)로 동일합니다. 따라서 성능의 우위는 시간 복잡도가 아닌 "공간 복잡도의 최적화"와 "목표 데이터의 분포 특징"에 의해 결정됩니다.