[Algorithm] 깊이 우선 탐색 (DFS) vs 너비 우선 탐색 (BFS)

BFS와 DFS의 개념을 정리하며 두 알고리즘의 본질적인 차이를 명확이 이해할 수 있어 좋았습니다. 알고리즘 공부를 하다 보면 정말 많이 나오는 유형인데 단순히 개념을 암기하는 것을 넘어서 큐와 스택이라는 자료구조가 어떻게 너비 우선 탐색, 깊이 우선 탐색이라는 상반된 방식을 만들어내는지 원리적으로 공부할 수 있어 좋았습니다.

기존에는 BFS와 DFS 중에 선택해서 풀 수 있는 문제가 많아 큰 기준을 두지 않고 편한 알고리즘을 위주로 구현했었는데, BFS가 최단 경로를 보장하는 대신 메모리 사용량이 크고 DFS는 메모리 효율을 보장하는 대신 최단 경로가 아니라는 명확한 트레이드오프 관걔를 파악한 후 상황에 맞는 알고리즘을 선택하는 기준이 생겼습니다. 공부한 내용을 바탕으로 앞으로는 이를 응용한 더 복잡한 문제에 도전해보려고 합니다.

---

1. 너비 우선 탐색 (BFS, Breadth-Firsth Search)

가까운 곳부터 넓게 탐색하는 방법

 

BFS는 시작 노드에서부터 가장 가까운 노드들부터 차례대로 탐색하는 방법입니다. 큐(Queue) 자료구조를 사용해 구현합니다.

 

1-1) 탐색 과정

1. 시작 노드를 큐에 넣고 방문 처리합니다.
2. 큐에서 노드를 하나 꺼냅니다.
3. 꺼낸 노드와 인접한 노드 중 아직 방문하지 않은 노드들을 모두 큐에 넣고 방문 처리합니다.
4. 큐가 빌 때까지 2-3번 과정을 반복합니다.

1-2) 장점

• 항상 최단경로를 보장합니다. 가중치가 없는 그래프에서 시작 노드로부터 특정 노드까지의 최단 경로를 찾아주기 때문에 길 찾기, sns 친구 찾기 등에 유용한 방법입니다.
• 노드 수에 비해 간선이 적은 그래프에서 DFS보다 빠르게 동작하기 때문에 최소 그래프에서 효율적인 방법입니다.

1-3) 단점

• 방문할 노드들을 모두 큐에 저장해야 하므로, 그래프가 넓고 깊이가 얕을 경우 많은 메모리를 사용할 수 있습니다.
• 찾은 경로는 항상 최단경로이므로 단순히 경로의 존재 여부만 확인하고 싶을 때는 비효율적일 수 있습니다.

1-4) 실사용 예시

• 지도 최단 거리 찾기 (가중치 없을 때)
  → A 지점에서 B 지점까지 가장 적은 수의 정거장을 거쳐 가는 경로를 찾을 때 사용됩니다.
• SNS 연결망 분석하기
  → '나와 친구인 사람', '내 친구의 친구인 사람'처럼 가까운 관계부터 순차적으로 탐색할 때 유용합니다.
  
• 웹 크롤러 동작 방식
  → 시작 페이지에서 링크된 페이지를 우선 방문하고, 그 다음 단계의 링크들을 방문하는 방식으로 웹사이트를 수집할 수 있습니다.
  

---

코드 예시

// 그래프는 인접 리스트 형태로 표현
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

const bfs = (graph, startNode) => {
  const visited = new Set(); // 방문한 노드를 기록
  const queue = [startNode]; // 탐색할 노드를 담는 큐
  const result = []; // 탐색 순서를 담는 배열

  visited.add(startNode);

  while (queue.length > 0) {
    const node = queue.shift(); // 큐의 가장 앞에서 노드를 꺼냄
    result.push(node);

    // 꺼낸 노드와 인접한 노드들을 확인
    graph[node].forEach((neighbor) => {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor); // 큐에 다음 탐색할 노드로 추가
      }
    });
  }

  return result;
};

console.log(bfs(graph, "A")); // 출력: [ 'A', 'B', 'C', 'D', 'E', 'F' ]

---

2. 깊이 우선 탐색 (DFS, Depth-Firsth Search)

한 길을 끝까지 파고들어 탐색하는 방법

 

DFS는 시작 노드에서부터 한 방향으로 갈 수 있을 때까지 최대한 깊이 들어가서 탐색하고, 더 이상 갈 곳이 없으면 이전 노드로 돌아와(backtracking) 다른 길을 탐색하는 방법입니다. 주로 스택(Stack)이나 재귀 함수를 사용해 구현합니다.

 

1-1) 탐색 과정

1. 시작 노드를 방문 처리합니다.
2. 시작 노드와 인접한 노드 중 아직 방문하지 않는 노드를 찾아 그 노드를 시작으로 재귀 호출을 합니다.
3. 인접한 노드를 모두 방문했다면 함수를 종료하고 이전 노드로 돌아갑니다.

1-2) 장점

• 현재 탐색 중인 경로만 저장하므로 BFS에 비해 메모리를 적게 사용합니다.
• 특정 경로가 존재하는지만 확인하고 싶을 때 운 좋게 해당 경로를 먼저 탐색한다면 빠르게 답을 찾을 수 있습니다.
• 재귀 함수를 사용하기 때문에 비교적 코드가 직관적이고 간결합니다.

1-3) 단점

• 가장 먼저 발견된 경로가 최단 경로가 아닐 수 있습니다.
• 그래프에 따라 매우 깊은 경로에 빠진다면 탐색이 끝나지 않는 무한 루프에 걸릴 수 있습니다.
  → 깊이를 제한해서 해결 가능

1-4) 실사용 예시

• 미로 찾기, 퍼즐 게임
  → 가능한 모든 경우의 수를 하나씩 시도해봐야 하는 문제에 적합합니다.
  
• 경로 존재 여부 확인하기
  'A에서 B까지 가는 길이 있는지?'와 같은 단순한 연결성 질문을 해결할 때 효율적입니다.
• 위상 정렬하기
  → 작업의 선후 관계가 정해져 있을 때, 어떤 순서로 작업을 처리해야 하는지 결정하는 데 사용됩니다.
  
• 그래프의 사이클 탐지하기
  → 그래프 내에 순환하는 경로가 있는지 확인할 때 사용됩니다.
  

---

코드 예시

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

const dfs = (graph, startNode) => {
  const visited = new Set(); // 방문한 노드를 기록
  const result = [];       // 탐색 순서를 담는 배열

  function recursiveDfs(node) {
    if (!node) return; // 베이스 케이스

    visited.add(node);
    result.push(node);

    // 인접한 노드를 깊이 우선으로 탐색
    graph[node].forEach((neighbor) => {
      if (!visited.has(neighbor)) {
        recursiveDfs(neighbor);
      }
    });
  }

  recursiveDfs(startNode);
  return result;
};

console.log(dfs(graph, "A")); // 출력: [ 'A', 'B', 'D', 'E', 'F', 'C' ] (순서는 인접 리스트 순서에 따라 달라질 수 있음)

---

BFS vs DFS 비교하기

구분	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
탐색 방식	수평적, 레벨 단위 탐색	수직적, 한 방향으로 깊게 탐색
자료구조	큐 (Queue) - 선입선출(FIFO)	스택 (Stack) - 후입선출(LIFO) 또는 재귀
속도	시작점과 가까운 노드를 찾을 때 빠름	목표가 깊은 곳에 있을 때 빠름
메모리	넓은 그래프에서 많이 사용	깊은 그래프에서 많이 사용 (경로 저장)
주요 용도	최단 경로 탐색 (가중치 없을 때)	경로의 존재 여부, 모든 경우의 수 탐색