BFS, DFS에 대해 설명하세요
Keyword
queue, stack, 정점, 간선
Script
BFS는 너비 우선 탐색으로, 그래프 상에서 시작되는 정점을 기준으로, 연결되어 있는 모든 정점을 탐색하는 알고리즘입니다. 마치 Tree의 Level Order 순회처럼 작동하며, 실제 구현에서는 queue를 사용하여 다음 탐색할 정점을 queue에 저장해둘 수 있습니다.
DFS는 깊이 우선 탐색으로, 그래프 상에서 시작되는 정점을 기준으로, 연결되어 있는 한 정점으로 계속해서 나아가다가 더이상 진행할 수 없을 때 다시 돌아오는 과정을 반복합니다. DFS 구현에서는 stack이 적절합니다.
두 탐색 모두 시간복잡도는 O(정점 개수 + 간선 개수) 입니다.
Additional
최단거리 문제
최단거리 문제에서는 BFS를 사용하는 것이 더 효율적이다. BFS는 시작 노드로부터 가까운 곳부터 찾기 때문에, 각 단계에 level을 매길 수 있다면 처음으로 목적지에 도달했을 때의 level이 최단 거리가 된다.
경로의 특징 문제
특정한 경로를 찾는 문제에서 특정 조건이 걸려있는 경우, DFS를 사용하는 것이 효율적이다. DFS를 사용하면 한 정점으로 계속해서 나아가기 때문에, 특정 조건에 해당하는 경로를 탐색하기에 유리하다.
with programming