글의 목적

DFS,BFS 에 대해 설명하는 글입니다.
기본적인 자료구조, 개념에 대한 이해를 설명하는 글입니다.

기본 개념

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

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

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

ex) 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때 까지 쭉 가다가 
더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와그 갈림길부터 
다시 다른 방향으로 탐색하는 방식을 깊이 우선 탐색 방식이다. 

• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택.
• 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단함
• 검색 속도 자체는 너비 우선 탐색에 비해서느림

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

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

주로 두 노드 사이의 최단 경로를 찾고 싶을 때, 이 방법을 선택한다.

ex 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 ,
Sam 과 Eddie 사이에 존재하는 경로를 찾는 경우

깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴볼 경우가 존재 (최악의 경우)
너비 우선 탐색의 경우 - SAM과 가까운 관계부터 탐색

DFS, BFS 비교

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다. DFS,BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

DFS와 BFS의 특징 & 문제 유형

• 그래프의 모든 정점을 방문하는 것이 주요한 문제
  -> 모든 정점을 방문하는 것이중요한 문제의 경우 DFS,BFS 두 가지 방법 어느 것을 사용하여도 상관없다.
• 경로의 특징을 저장해둬야 하는 문제
  -> 예를 들어 각 정점에 숫자가 적혀 있고 A부터 B까지 가는 경로를 구하는데 경로에 같은 문제가 있으면 안된다. 라는 조건이 있을 경우, DFS를 사용한다 (BFS는 경로의 특징을 표현할 수 없다)
• 최단거리 구해야 하는 문제
  미로 찾기 등 최단거리를 구해야할 경우, BFS가 유리하다.
  왜냐하면, 깊이 우선 탐색으로 경로를 검색할 경우 발견되는 해답이 최단거리가 아닐 수 있지만,
  너비 우선탐색으로 현재 노드에서 가까운 곳부터찾기 때문에 경로를 탐색시 먼저 찾아지는 해답이 곧 최단거리이다.