너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)
너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)
너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)은 그래프나 트리 구조의 모든 정점을 방문(탐색)하기 위한 가장 기본적인 두 가지 알고리즘입니다. 두 알고리즘은 정점을 탐색하는 순서에서 핵심적인 차이를 보이며, 문제의 성격에 따라 적절한 알고리즘을 선택해야 합니다.
🌐 너비 우선 탐색 (BFS, Breadth-First Search)
- 개념 (Concept) : 루트(또는 임의의 시작 정점)에서 시작하여, 인접한 정점들을 먼저 모두 방문하는 방식입니다. 즉, 현재 정점에서 가까운 곳부터 넓게 탐색하는 것을 우선으로 합니다.
- 동작 원리
1. 시작 정점을 큐(Queue)에 넣고 방문 처리합니다. 2. 큐에서 정점을 하나 꺼냅니다. 3. 꺼낸 정점과 인접한 모든 정점들 중, 아직 방문하지 않은 정점들을 모두 큐에 넣고 방문 처리합니다. 4. 큐가 빌 때까지 2-3번 과정을 반복합니다.
- 핵심 자료구조 : 큐 (Queue) (선입선출, FIFO)
- 특징 및 활용
> * 두 정점 사이의 최단 경로(가중치가 없는 경우)를 찾는 데 사용됩니다. > * 레벨 순서대로 순회하는 특징이 있습니다. > * 네트워크 브로드캐스트, 소셜 네트워크에서 연결된 친구 찾기 등에 활용됩니다.
🌲 깊이 우선 탐색 (DFS, Depth-First Search)
- 개념 (Concept) : 루트(또는 임의의 시작 정점)에서 시작하여, 한 분기를 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 이전 분기로 돌아와 다른 분기를 탐색하는 방식입니다. 즉, 깊게 탐색하는 것을 우선으로 합니다.
- 동작 원리 (재귀 사용)
1. 시작 정점을 방문 처리하고, 이 정점을 기준으로 재귀 호출을 시작합니다. 2. 현재 정점과 인접한 모든 정점들 중, 아직 방문하지 않은 정점을 찾아 그 정점을 기준으로 재귀 호출을 합니다. 3. 더 이상 방문할 인접 정점이 없으면, 함수 호출을 종료하고 이전 정점으로 돌아갑니다.
- 핵심 자료구조 : 스택 (Stack) (후입선출, LIFO). 재귀 함수로 구현 시에는 시스템의 함수 호출 스택이 이 역할을 대신합니다.
- 특징 및 활용
> * 그래프의 모든 정점을 방문하고자 할 때 주로 사용됩니다. > * 경로의 존재 여부, 사이클 탐지, 위상 정렬(Topological Sort) 등에 활용됩니다. > * 백트래킹(Backtracking) 알고리즘의 기반이 됩니다.
💡 개발자 핵심 Point
| 특징 | BFS | DFS | |---|---|---| | 탐색 방식 | 넓게 (인접 정점 우선) | 깊게 (한 방향 우선) | | 자료구조 | 큐 (Queue) | 스택 (Stack), 재귀 | | 속도 | 일반적으로 DFS보다 느릴 수 있음 | 일반적으로 BFS보다 빠를 수 있음 | | 메모리 | DFS보다 더 많은 메모리 필요 | BFS보다 적은 메모리 필요 | | 최단 경로 | 보장 (가중치 없을 때) | 보장하지 않음 |
- 문제의 요구사항에 따라 적절한 탐색 방법을 선택해야 합니다.
> * "최단 거리를 찾아라" → BFS > * "모든 경로를 탐색해봐라" → DFS > * "연결되어 있는지 확인해라" → 둘 다 가능 (보통 DFS가 더 간단)
- 코딩 테스트에서 그래프 관련 문제가 나오면, 가장 먼저 BFS와 DFS 중 어떤 것을 적용할지 고민하는 것이 문제 해결의 시작입니다.
