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

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

 

개념

• 한 노드를 방문하면 그 노드와 연결된 이웃을 끝까지 따라가며 탐색하는 방식
• 한 길로 끝까지 파고 들어갔다가, 막히면 돌아와서 다른 길로 탐색

동작 방식

1. 시작 노드를 방문 표시
2. 방문하지 않은 인접 노드로 이동 → 방문 표시
3. 더 이상 이동할 곳이 없으면 되돌아옴(백트래킹)
4. 모든 노드를 방문할 때까지 반복

구현 방법

• 재귀 (스택 역할을 호출 스택이 함)
• 명시적인 스택 자료구조 사용

장점

• 구현이 간단함 (재귀 사용 시)
• 경로 탐색, 백트래킹, 순열/조합 문제에 유리

단점

• 경로가 길면 스택 오버플로우 가능
• 최단 거리 보장 안 함

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

 

개념

• 시작 노드에서 가까운 노드부터 차례대로 방문
• 파동처럼 퍼져 나감

동작 방식

1. 시작 노드를 방문 표시 후 큐에 넣음
2. 큐에서 노드를 꺼냄
3. 해당 노드의 방문하지 않은 모든 인접 노드를 큐에 넣음
4. 큐가 빌 때까지 반복

구현 방법

• 큐 자료구조 사용 (LinkedList, ArrayDeque 등)

장점

• 최단 거리 보장 (모든 간선의 가중치가 같을 때)
• 레벨별 탐색 가능

단점

• 큐에 많은 노드가 쌓일 수 있어 메모리 사용량이 커짐

 

시각적 비교

 

1
| \
2  3
|  |
4  5

DFS 순서 (깊이 우선): 1 → 2 → 4 → (돌아옴) → 3 → 5

BFS 순서 (너비 우선): 1 → 2 → 3 → 4 → 5