DFS vs BFS

DFS와 BFS의 차이점과 문제에 좀 더 알맞는 풀이에 대해 정리

DFS와 BFS의 차이점과 문제에 맞닥뜨렸을때 어떤것을 활용해야할지 판단이 안서서 정리해본다.

DFS와 BFS의 특징

모두 그래프를 탐색하는 방법이다.
그래프란, 정점(node) 과 그 정점을 연결하는 간선(edge) 으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한번씩 방문하는것을 말한다.

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

루트 노트 (또는 임의의 노드)에서 시작해서 , 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방식

Ex) 미로 찾기

특징

• 모든 노드를 방문하고자 하는 경우 이 방법 택함
• DFS가 BFS에 비해 조금 더 간단
• 검색 속도 자체는 BFS가 DFS보다 빠름

BFS(Breadth-First-Search, 너비 우선 탐색)

루트 노드(또는 임의의 노드) 에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법

두 노드 사이의 최단 경로를 찾고 싶을때 이 방법 사용

Ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현했을때 두 사람 사이 존재하는 경로를 찾는 경우

---

DFS vs BFS

DFS	BFS
현재 정점에서 갈 수 있는 정점까지 들어가며 탐색	현재 정점에서 인접한 정점(가까운)부터 탐색
stack또는 재귀로 구현	queue를 이용하여 구현

---

⭐️ 그렇다면 어떤것이 어떤 유형에 적합할까

DFS/BFS 무관

• 그래프의 모든 정점을 방문하는것이 주요한 문제 > 둘중 편한것으로 작성

DFS

• 경로의 특징을 저장해둬야할 경우
• 검색 대상 그래프가 너무 클 경우

BFS

• 최단 거리 구해야하는 문제 > 현재 노드에서 가까운 곳부터 찾기 때문에 처음 찾아지는 정답이 곧 해답
• 검색 대상 그래프 크지 않을 경우
• 검색 시작 지점과 원하는 대상이 별로 멀지 않을 경우