알고리즘에서 '너비 우선 탐색(BFS, Breadth-First Search)'과 '깊이 우선 탐색(DFS, Depth-First Search)'의 차이점은?

쉬움 freeCodeCamp

보기 및 정답

A BFS와 DFS는 탐색 순서와 자료구조 사용 방식이 동일하며, 항상 같은 순서의 결과를 반환한다

B BFS는 가까운 노드부터 층별로 탐색하고(큐 사용), DFS는 한 경로를 끝까지 탐색한 후 되돌아온다(스택/재귀 사용)

C DFS가 어떤 그래프에서든 항상 BFS보다 탐색 속도가 빠르며, 메모리 사용량도 항상 더 적다

D BFS는 트리 자료구조에서만 사용할 수 있고, DFS는 일반 그래프 구조에서만 사용 가능하며 두 방식은 서로 호환되지 않는다

BFS는 큐를 사용하여 시작 노드에서 거리가 가까운 노드부터 탐색하므로 최단 경로 탐색에 적합합니다. DFS는 스택이나 재귀를 사용하여 한 방향으로 깊이 탐색한 후 백트래킹합니다. 미로 탈출이나 경로 존재 여부 확인에는 DFS가, 최단 경로에는 BFS가 적합합니다.

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

로그인