DFS와 BFS, 어디에 활용될까?
그래프 이론에서 가장 기본적이면서도 강력한 두 가지 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색)과 BFS(Breadth First Search, 너비 우선 탐색)는 단순한 그래프 순회를 넘어 컴퓨터 과학 전반에서 폭넓게 활용되고 있습니다. 이번 글에서는 두 알고리즘이 실제로 어떤 문제를 해결하는 데 쓰이는지 대표적인 응용 사례를 살펴보겠습니다.
DFS(깊이 우선 탐색)의 주요 응용
DFS는 한 경로를 끝까지 깊이 탐색한 뒤 되돌아오는 방식으로 동작하며, 다음과 같은 용도로 활용됩니다.
- 최소 신장 트리 생성: 가중치가 없는 그래프에 DFS를 수행하면, 모든 정점 간 최단 경로 트리가 되는 최소 신장 트리(spanning tree)를 만들 수 있습니다.
- 사이클 검출: DFS 수행 중 역방향 간선(back edge)이 발견되면 그래프에 사이클이 존재한다는 것을 판별할 수 있습니다.
- 경로 탐색: 두 정점 u와 v 사이에 경로가 존재하는지 확인하고, 실제 경로를 찾아내는 데 사용할 수 있습니다.
- 위상 정렬(Topological Sorting): 작업 간의 의존 관계가 주어졌을 때 작업 수행 순서를 결정하는 위상 정렬은 DFS를 기반으로 구현할 수 있습니다.
- 강연결 성분(SCC) 찾기: 모든 정점에서 다른 모든 정점으로의 경로가 존재하는 경우를 강연결(strongly connected)이라 하며, DFS를 이용해 그래프의 강연결 성분을 효율적으로 찾을 수 있습니다.
BFS(너비 우선 탐색)의 주요 응용
BFS는 시작 정점에서 가까운 노드부터 차례로 넓게 탐색하는 방식으로, 실생활의 다양한 시스템에서 활용되고 있습니다.
- P2P 네트워크: 비트토렌트(BitTorrent) 같은 피어 투 피어(P2P) 네트워크에서 인접한 모든 노드를 찾는 데 BFS가 사용됩니다.
- 검색 엔진 크롤러: 구글 등 검색 엔진의 크롤러는 BFS 방식으로 웹 페이지를 색인합니다. 시작 페이지에서 출발해 해당 페이지의 모든 링크를 따라가며 새로운 페이지를 수집합니다.
- GPS 내비게이션: GPS 내비게이션 시스템에서 현재 위치 주변의 인접 장소를 찾는 데 BFS가 활용됩니다.
- 네트워크 브로드캐스팅: 네트워크에서 패킷을 모든 노드에 전송(broadcast)해야 할 때 BFS 알고리즘이 사용됩니다.
- 경로 찾기 알고리즘: 미로 찾기 등 다양한 경로 탐색 알고리즘은 BFS 또는 DFS를 기반으로 설계됩니다.
- 최대 유량 계산: 포드-풀커슨(Ford-Fulkerson) 알고리즘에서 증가 경로를 찾기 위해 BFS가 활용되어 네트워크의 최대 유량(max flow)을 구하는 데 사용됩니다.
마무리
DFS는 위상 정렬, 사이클 검출, 연결 성분 분석처럼 그래프의 구조적 특성을 파악하는 문제에 강점을 보이고, BFS는 최단 거리 탐색, 레벨 순회, 네트워크 확산처럼 가까운 요소부터 순서대로 처리해야 하는 문제에 적합합니다. 두 알고리즘의 특성과 응용 분야를 정확히 이해하면 실제 개발 상황에서 더 나은 해결책을 선택할 수 있습니다.