DFS, BFS

DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

 

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

DFS는 말 그대로 한 길로 끝까지 파고드는 탐색 방식입니다.

현재 노드에서 가능한 한 깊게 내려간 뒤, 더 이상 진행할 수 없을 때 되돌아옵니다. 즉, 스택(Stack) 또는 재귀(Recursion) 기반으로 동작합니다.

작동 원리

A
├── B
│   ├── D
│   └── E
└── C
    └── F

 

탐색 순서

A → B → D → (되돌아옴) → E → (되돌아옴) → C → F

예시

function DFS(graph: Record<string, string[]>, start: string, visited = new Set<string>()) {
  console.log(start);
  visited.add(start);

  for (const next of graph[start]) {
    if (!visited.has(next)) {
      DFS(graph, next, visited);
    }
  }
}

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

DFS(graph, "A"); // 출력: A B D E C F

특징

• 자료구조: Stack 또는 재귀 호출
• 탐색 방향: 깊이 우선
• 사용 예시: 백트래킹, 조합/순열, 미로 탐색, 여행 경로 문제 등

 

---

 

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

BFS는 DFS와 반대로 가까운 노드부터 차례대로 탐색합니다. 즉, 한 단계씩 넓게 퍼져나가며 탐색합니다. 이때는 큐(Queue) 자료구조를 사용합니다.

작동 원리

A
├── B
│   ├── D
│   └── E
└── C
    └── F

 

탐색 순서:

A → B → C → D → E → F

예시

function BFS(graph: Record<string, string[]>, start: string) {
  const visited = new Set<string>();
  const queue: string[] = [start];

  while (queue.length > 0) {
    const node = queue.shift()!;
    console.log(node);
    visited.add(node);

    for (const next of graph[node]) {
      if (!visited.has(next)) {
        queue.push(next);
      }
    }
  }
}

BFS(graph, "A"); // 출력: A B C D E F

 

특징

• 자료구조: Queue (FIFO)
• 탐색 방향: 너비 우선
• 사용 예시: 최단 거리 탐색, 네트워크 연결, 레벨별 탐색

 

---

 

DFS vs BFS 비교

 

구분	DFS	BFS
탐색 구조	스택 / 재귀	큐
탐색 방향	깊이 우선	너비 우선
구현 난이도	재귀적으로 간단	반복문 + 큐로 직관적
장점	모든 경로 탐색에 유리	최단 거리 탐색에 유리
예시 문제	여행경로, 미로 탐색, 조합	최단 거리, 네트워크, 토마토 문제

 

상황	DFS	BFS
미로 탐험	한 길로 끝까지 들어갔다가 막히면 되돌아옴	출발점에서 한 칸씩 사방으로 퍼져나감
전화 트리	친구 한 명에게 전화 → 그 친구의 친구에게 → 반복	내 친구 모두에게 동시에 전화

 

 

 

---

 

언제 DFS, BFS?

문제 유형	추천 탐색 방식
모든 가능한 경우 탐색 (백트래킹, 순열, 조합)	DFS
최단 거리, 최소 이동 횟수 문제	BFS
네트워크 연결, 그래프 컴포넌트 세기	DFS 또는 BFS 둘 다 가능

• DFS는 깊게, BFS는 넓게 본다.
• DFS는 백트래킹에 강하고, BFS는 최단 거리에 강하다.