[면접 준비] DFS와 BFS의 차이

학습 키워드: DFS, BFS

 

2024-08-01 면접 카타 질문

DFS와 BFS의 차이를 말해주세요:

 트리나 그래프 구조의 데이터에서 루트 노드부터 한 방향으로 깊이 우선 탐색하고, 원하는 결과를 찾지 못했다면 상위 노드로 돌아가 방문하지 않은 다른 갈림길에 있는 노드를 탐색하는 방식을 DFS라고 부릅니다. DFS는 스택이나 재귀 함수로 구현되며, 깊이 우선으로 방문한다는 특징으로 인해 최초 방문한 노드까지의 경로가 최단거리가 아닐 수 있습니다.

 

 BFS는 루트 노드에서 시작하여 같은 depth의 인접 노드 전체를 훑고 그 다음 depth를 훑는 방식입니다. BFS는 queue를 사용하여 구현되며, 가장 가까운 노드부터 탐색한다는 특징으로 인해 최초 방문한 노드까지의 경로가 항상 최단거리가 됩니다. 그렇다고 해서 BFS가 DFS보다 항상 유리한 것은 아닌데, BFS의 경우 같은 depth인 모든 노드의 정보를 저장해야하기 때문에 DFS에 비해 메모리 사용률이 높습니다. 따라서 방대한 크기의 그래프 등을 탐색하게 되면 효율이 나쁩니다.

 

 

--