알고리즘 | BFS vs DFS

BFS vs DFS in JavaScript

그래프 탐색 알고리즘 중 가장 대표적인 두 가지는 BFS (너비 우선 탐색)과 DFS (깊이 우선 탐색) 입니다. 둘은 노드를 탐색하는 순서와 방식이 다르며, JS에서는 사용하는 자료구조에 따라 구분됩니다.

---

🧠 탐색 알고리즘이란?

그래프 구조(노드와 간선으로 이루어진 구조)에서 어떤 노드부터 출발해서 다른 노드들을 방문하는 방법 입니다.

---

🎯 두 가지 주요 탐색 방식

이름	뜻	언제 꺼내는가	구조	우선순위
BFS (Breadth-First Search)	너비 우선 탐색	먼저 들어간 것부터	Queue (FIFO)	가까운 노드부터
DFS (Depth-First Search)	깊이 우선 탐색	최근 들어간 것부터	Stack (LIFO)	깊이 파고들기

---

💡 비유로 이해하기

• BFS: 사람 많은 건물에서 층별로 돌아다니는 느낌 (넓게 퍼짐)
• DFS: 미로 찾기처럼 한 방향으로 끝까지 가보다가 막히면 돌아오는 느낌 (깊게 탐색)

---

👨‍💻 예시: 그래프 구조

예시 연결:
1 - 2 - 3
|
4

const graph = {
  1: [2, 4],
  2: [1, 3],
  3: [2],
  4: [1]
};

---

🔵 BFS: 너비 우선 탐색 (Queue 사용)

💭 흐름

1. 큐에 시작 노드 넣기 → queue = [1]
2. 큐에서 꺼내서 처리 → 1 꺼냄
3. 1의 이웃(2, 4)을 큐에 추가 → queue = [2, 4]
4. 2 꺼냄, 2의 이웃(3)을 추가 → queue = [4, 3]
5. 4 꺼냄 → 이미 방문한 1은 제외 → queue = [3]
6. 3 꺼냄 → 끝

function bfs(start, graph) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);

  while (queue.length) {
    const node = queue.shift();  // 앞에서 꺼냄
    console.log(node);           // 방문 처리
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);    // 뒤에 넣음
      }
    }
  }
}

📊 도식 흐름 (Queue)

[1]       => 1 방문 → [2,4]
[2,4]     => 2 방문 → [4,3]
[4,3]     => 4 방문 → [3]
[3]       => 3 방문 → [] (종료)

---

🔴 DFS: 깊이 우선 탐색 (Stack 사용)

💭 흐름

1. 스택에 시작 노드 넣기 → stack = [1]
2. 스택에서 꺼내기 → 1 꺼냄
3. 1의 이웃(2, 4)을 스택에 넣기 → stack = [2, 4]
4. 4 꺼냄 → 이웃 1은 이미 방문 → stack = [2]
5. 2 꺼냄 → 이웃 3 넣기 → stack = [3]
6. 3 꺼냄 → 끝

function dfs(start, graph) {
  const visited = new Set();
  const stack = [start];
  visited.add(start);

  while (stack.length) {
    const node = stack.pop();   // 뒤에서 꺼냄
    console.log(node);          // 방문 처리
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);   // 뒤에 넣음
      }
    }
  }
}

📊 도식 흐름 (Stack)

[1]       => 1 방문 → [2,4]
[2,4]     => 4 방문 → [] (이미 방문)
[2]       => 2 방문 → [3]
[3]       => 3 방문 → [] (종료)

---

✅ 정리 요약

• BFS 활용:

  • 최단 거리 탐색이 필요한 경우 (예: 미로 문제, 최단 경로 계산)
  • 가까운 노드부터 순차적으로 탐색해야 할 때
  • 단계적으로 퍼져나가는 문제 (ex. 전염, 확산 문제)
  • queue.push() + queue.shift()

• DFS 활용:

  • 모든 경로를 탐색해야 하는 경우 (예: 백트래킹, 퍼즐, 조합)
  • 트리/그래프의 깊이를 우선적으로 보고 싶을 때
  • 재귀적 성격이 강한 문제 (예: 구조적 반복, 순열 생성)
  • stack.push() + stack.pop()

⏱️ 시간적으로 유리한 탐색은?

• BFS는 stack.pop()을 사용하므로 JavaScript에서 O(1)로 매우 빠름
• DFS는 queue.shift()를 쓰면 O(N) 시간이 걸려 느림 (앞에서 꺼내며 모든 요소 밀어야 함)
• 따라서 1초 제한 같은 시간 민감한 문제에서는 BFS가 구조적으로 더 유리함
• 단, 문제 성격에 따라 꼭 DFS가 필요한 경우도 있음 (예: 최단 거리)

---

🧩 탐색 방식에 꼭 맞는 문제 예시

문제 상황	적합한 탐색 방식	이유
미로에서 출구까지 최소 칸 수	BFS	가까운 길부터 탐색 → 최단 거리 보장
말이 이동해서 목적지에 도달 (체스판)	BFS	같은 비용으로 여러 방향 이동 → 가장 빠른 경로 탐색
친구의 친구 추천 (n단계 이내)	BFS	거리(단계)를 기준으로 퍼짐
모든 가능한 경로 탐색 (순열/조합)	DFS	깊이 우선으로 재귀 탐색 구조에 적합
백트래킹 문제 (N-Queen, 스도쿠)	DFS	조건이 틀리면 바로 가지치기 가능