오늘은 DFS와 BFS를 쉽고 확실하게 이해해보기

소개

알고리즘 면접에서 가장 기본이면서도 자주 등장하는 탐색 기법 두 가지,
바로 DFS (깊이 우선 탐색) 과 BFS (너비 우선 탐색) 다.

이 두 개념은 자료구조(트리/그래프) 에서 데이터를 어떤 순서로 탐색할 것인지 결정할 때 사용된다.
웹 개발을 하더라도, 트리 구조인 DOM을 다루면서 자연스럽게 만나게 된다.

목차

✔ 개념
✔ JavaScript 실습 예제
✔ 두 방법의 차이
✔ 언제 어떤 걸 쓰면 좋은지

사용 될 🌲tree 구조

const tree = {
  value: 'A',
  children: [
    {
      value: 'B',
      children: [
        { value: 'D', children: [] },
        { value: 'E', children: [] }
      ]
    },
    {
      value: 'C',
      children: [
        { value: 'F', children: [] }
      ]
    }
  ]
};

DFS 🔎 (Depth First Search) - 깊이 우선 탐색

말 그대로 깊숙하게 탐색하는 방식이다.

📍 흐름 요약
1. 현재 노드 처리
2. 자식 노드 중 첫 번째부터 끝까지 깊이 들어간다.
3. 더 이상 갈 곳 없으면 되돌아오기

📍 사용 자료구조
- 스택(stack) 또는 재귀(함수 스택)

📍 코드 예시

function DFS(node) {
  if (!node) {
    return null;
  }
  console.log(node.value)
  
  for (const child of node.children) {
    DFS(child); 
  }
}

// 출력값 -> A B D E C F

그림으로 이해하기

재귀 스택: (함수 호출 순서)
DFS(A)
 └─ DFS(B)
     ├─ DFS(D) -> 종료
     └─ DFS(E) -> 종료
 └─ DFS(C)
     └─ DFS(F) -> 종료

✅핵심 이해 포인트

• DFS는 재귀 호출 스택을 이용해 “한 노드의 모든 자식 → 그 다음 자식” 순으로 처리
• 현재 노드의 자식들을 순서대로 모두 탐색 후에야, 부모 노드로 돌아가 다음 형제 노드를 처리
• 따라서 B의 모든 자식을 처리한 뒤에야 A의 두 번째 자식 C로 넘어가는 것

BFS 🌊 (Breadth First Search) - 너비 우선 탐색

말 그대로 같은 레벨(깊이)부터 탐색하는 방식이다.

📍 흐름 요약
1. 현재 노드 방문
2. 같은 레벨의 모든 자식 노드를 큐에 넣고 순서대로 처리
3. 더 이상 처리할 노드가 없으면 종료

📍 사용 자료구조
- 큐(queue) 또는 배열 + 포인터(shift 대신 index 사용 추천)

📍 코드 예시

function BFS(root) {
  const queue = [root];
  let index = 0; // 큐의 읽기 위치 포인터

  while (index < queue.length) {
    const node = queue[index++]; // dequeue
    console.log(node.value);

    for (const child of node.children) {
      queue.push(child); // enqueue
    }
  }
}

// 출력값 -> A B C D E F

그림으로 이해하기

큐 상태(순차 처리):

시작: [A]
방문 A -> 큐: [B, C]
방문 B -> 큐: [C, D, E]
방문 C -> 큐: [D, E, F]
방문 D -> 큐: [E, F]
방문 E -> 큐: [F]
방문 F -> 큐: []

✅핵심 이해 포인트

• BFS는 큐를 이용해 같은 레벨의 노드를 먼저 처리
• 깊이보다 넓이 우선 → 가까운 노드를 먼저 탐색
• index 포인터 사용 이유:
  • js 배열 shift()는 O(n) 비용 발생
  • 포인터 사용 시 O(1)로 효율적

DFS vs BFS 비교

항목	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
자료구조	스택 / 재귀 호출 스택	큐
탐색 순서	한 방향으로 깊게	레벨 단위, 넓게
장점	백트래킹, 전체 경로 탐색, 메모리 효율적(얕고 깊은 트리)	최단 거리 보장, 가까운 노드 우선 탐색, 레벨별 처리 용이
단점	최단 경로 보장 X, 깊이 깊으면 스택 오버플로우	넓은 트리에서 메모리 많이 사용

언제 어떤 걸 쓰면 좋을까? 🤔

- DFS 선택 시

• 전체 경로/조합/백트래킹 문제
• 깊은 트리 탐색, 특정 조건 만족 시 종료
• 메모리가 넉넉하고 트리가 깊고 좁을 때 유리

- BFS 선택 시

• 최단 경로 탐색
• 같은 레벨 단위 처리 필요
• 트리가 넓고 얕거나, 가까운 노드를 먼저 찾아야 할 때

오늘은 여기까지 DFS와 BFS에 대해서 간략하게 알아봤다
뿌듯하다.