막다른 길까지 파고드는 깊이 우선 탐색
크리스는 쇼핑몰의 '카테고리 메뉴'를 만들고 있다.
[전자제품 > 컴퓨터 > 노트북 > 게이밍 노트북] 처럼 카테고리는 끝없이 깊어질 수 있다.
크리스는 "게이밍 노트북"이라는 특정 카테고리를 찾아서 화면에 보여주고 싶다.
그런데 데이터 구조가 트리(Tree) 형태로 얽혀있다.
"배열은 for 문으로 돌면 되는데, 이렇게 가지치기된 데이터는 어떻게 순회해야 하지?"
이때 사용하는 탐색 방법은 크게 두 가지다.
오늘은 미로 찾기의 정석이자, 재귀 함수의 꽃인 DFS를 먼저 알아보자.
1. 미로 찾기의 정석: "한 우물만 판다"
DFS의 원리는 미로 찾기와 똑같다.
갈림길이 나오면 무조건 한쪽 길(예: 왼쪽)을 선택해서 막다른 골목이 나올 때까지 직진한다.
막다른 길에 다다르면? 바로 직전의 갈림길로 되돌아가서(Backtrack) 가보지 않은 다른 길을 탐험한다.
2. 구현의 핵심: 스택(Stack)과 재귀(Recursion)
DFS를 구현하는 가장 쉬운 방법은 재귀 함수를 쓰는 것이다.
함수가 함수를 호출하면 컴퓨터의 콜 스택(Call Stack)에 작업이 쌓이는데, 이 스택 구조가 DFS의 "갔던 길을 되돌아오는" 과정과 완벽하게 일치하기 때문이다.
자바스크립트 구현 (트리 순회)
간단한 트리 객체가 있다고 가정해 보자.
const tree = {
name: "Root",
children: [
{
name: "A",
children: [
{ name: "A-1", children: [] },
{ name: "A-2", children: [] }
]
},
{
name: "B",
children: [
{ name: "B-1", children: [] }
]
}
]
};
function dfs(node) {
// 1. 현재 노드 처리 (방명록 작성)
console.log("방문:", node.name);
// 2. 자식들을 순서대로 재귀 호출 (더 깊이 들어감)
if (node.children) {
node.children.forEach(child => {
dfs(child);
});
}
}
dfs(tree);
// 출력 순서: Root -> A -> A-1 -> A-2 -> B -> B-1코드가 놀랍도록 단순하다. forEach로 자식을 부르는 순간, 코드의 실행 흐름은 자식 노드의 깊숙한 곳으로 먼저 빨려 들어간다. 이것이 DFS다.
3. 언제 써야 할까? (Use Cases)
DFS는 "경로의 특징"을 저장해야 하거나, "모든 노드를 방문"해야 할 때 유리하다.
4. 주의할 점: 무한 루프의 늪
만약 데이터가 트리가 아니라, 서로 꼬리를 무는 그래프(Graph) 형태라면 조심해야 한다.
A가 B를 가리키고, B가 다시 A를 가리킨다면?
dfs(A) -> dfs(B) -> dfs(A) -> ... 영원히 끝나지 않는다.
이를 방지하기 위해 방문 처리(Visited)가 필수다.
const visited = new Set(); // 방문 도장 찍을 곳
function dfsGraph(node) {
if (visited.has(node)) return; // 이미 왔던 곳이면 뒤로 돌아갓!
visited.add(node); // 도장 꾹
console.log(node);
node.neighbors.forEach(neighbor => dfsGraph(neighbor));
}핵심 정리
"아니, 나는 서울에서 부산 가는 가장 빠른 길을 찾고 싶다고!"
최단 거리를 보장해야 한다면, 한 우물만 파는 DFS는 좋은 선택이 아니다.
호수에 돌을 던지면 물결이 동그랗게 퍼져나가듯, 가까운 곳부터 차근차근 탐색하는 BFS(너비 우선 탐색)를 배워보자.