BFS와 DFS의 차이와 사용 사례를 설명해주세요.

BFS와 DFS는 그래프나 트리를 순회하는 대표 알고리즘입니다. BFS는 가까운 정점부터 레벨 순서로 탐색하고, DFS는 한 경로를 끝까지 깊게 들어간 뒤 되돌아옵니다. 탐색 순서 차이가 최단 거리, 경로 탐색, 상태 공간 탐색의 적합성을 나눕니다.

핵심 개념

• BFS는 Queue를 사용하고, 가중치가 없는 그래프의 최단 경로를 찾을 수 있습니다.
• DFS는 재귀 또는 Stack을 사용하며, 연결 요소, 사이클, 백트래킹, 위상 정렬 등에 자주 쓰입니다.
• 둘 다 방문 처리(visited)를 통해 중복 탐색과 무한 루프를 방지합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    for (const next of graph.get(node) ?? []) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
  }
}

function dfs(graph, node, visited = new Set()) {
  visited.add(node);
  for (const next of graph.get(node) ?? []) {
    if (!visited.has(next)) dfs(graph, next, visited);
  }
}

실무에서 주의할 점

• DFS 재귀는 그래프가 깊으면 call stack overflow가 발생할 수 있습니다.
• BFS는 frontier가 커질 수 있어 메모리 사용량이 큽니다.
• 가중치가 있는 최단 경로에는 일반 BFS가 아니라 다익스트라나 Bellman-Ford가 필요합니다.

실무 적용 가이드

• 최소 이동 횟수/가장 가까운 답은 BFS를 먼저 고려합니다.
• 모든 경우를 깊게 시도하거나 구조를 분해해야 하면 DFS를 고려합니다.
• 방문 시점을 큐에 넣을 때로 할지 꺼낼 때로 할지 일관되게 정합니다.

함께 연결해서 보면 좋은 키워드

BFS, DFS, Graph Traversal, Queue, Stack

정리

BFS와 DFS는 그래프나 트리를 순회하는 대표 알고리즘입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.