DFS와 BFS 완벽 이해: 그래프 탐색의 두 축

DFS와 BFS는 그래프·트리를 탐색하는 두 가지 기본 전략입니다. 코딩테스트에서 가장 자주 나오는 주제이므로 차이를 확실히 잡아둡시다.

한 문장 요약

• DFS(깊이 우선): 한 길로 끝까지 갔다가 막히면 되돌아온다 → 스택/재귀
• BFS(너비 우선): 가까운 곳부터 물결처럼 퍼진다 → 큐

DFS: 재귀로 깊이 파고들기

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

경로 탐색, 백트래킹(조합·순열), 사이클 검사, 연결 요소 세기에 잘 맞습니다.

BFS: 큐로 한 겹씩 퍼지기

function bfs(start, graph) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    for (const next of graph[node]) {
      if (!visited.has(next)) { visited.add(next); queue.push(next); }
    }
  }
}

핵심 차이: 최단 거리는 BFS

가중치가 없는 그래프에서 최단 거리는 BFS가 보장합니다. 가까운 노드부터 방문하기 때문입니다. DFS는 먼저 닿은 경로가 최단이라는 보장이 없습니다.

용도	추천
가중치 없는 최단 거리	BFS
모든 경로·조합 탐색	DFS(백트래킹)
미로 최소 이동	BFS
깊은 재귀 위험(스택 오버플로)	BFS 또는 반복 DFS

흔한 실수

• 방문 체크 시점: BFS는 큐에 넣을 때 방문 표시해야 중복 방지(꺼낼 때 하면 같은 노드가 여러 번 큐에 들어감)
• queue.shift()는 O(n) → 큰 입력은 인덱스 포인터나 덱 사용

마무리 체크리스트

• DFS = 스택/재귀, BFS = 큐
• 무가중치 최단거리는 BFS
• 조합·백트래킹은 DFS
• BFS는 넣을 때 방문 표시
• 가중치 있으면 다익스트라로 확장

두 탐색의 "언제"만 구분하면 그래프 문제의 출발선은 통과한 것입니다.