[Algorithm] DFS와 BFS 차이

알고리즘 공부 할 때 빠르게 기억해 낼 수 있게 적는 글!

 

DFS (Depth-First Search, 깊이 우선 탐색)

- 먼저, 하나의 깊이가 끝날 때까지 쭉 가다가 막히면은 다시 원래의 갈림길로 돌아와서 또다시 깊이 탐색하는 방법

- 모든 노드를 방문하고자 할 때 사용

- 스택 또는 재귀 함수 사용 (알고리즘을 이해하면 재귀 함수가 더 사용하기 쉬운듯)

 - 스택은 pop만 가능하니까 계속 뒤에꺼를 pop, pop 하니깐 깊은 곳으로 가게되는 거임 (잊지마!)

- 재귀는 깊이 탐색 시 삽입된 순서대로 탐색해서 왼쪽 분기부터 타고 가는데, 스택은 삽입된 순서의 역순서(pop으로 인한 역순서) 이기 때문에 오른쪽 분기부터 타고 내려감 (그러니깐 결과는 다를 수 있음)

- 재귀를 사용 할 수 있어서 코딩 적으로 DFS가 BFS보다 간단함

- 하지만, 깊이 끝까지 다 한번씩 돌면서 검색하기 때문에 BFS 보다 속도는 느림

 

.BFS (Breadth-First Search)

 

- 최단 경로를 찾고 싶을 때 사용

- deque 사용해서 popleft 함수 사용

- 가장 가까운 노드 탐색

 

 

- 경로를 직접적으로 구해야 하는 문제는 DFS 사용

- 최단 거리 구해야하는 경우는 BFS 사용

 

- 검색 대상이 작다면 BFS 사용

 

- 둘의 시간 복잡도는 O(N)

 

 

Reference : https://developer-mac.tistory.com/64, https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90