[Algorithm] DFS( Depth-First Search), BFS(Breadth-First Search)

1. DFS

최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동

로투 노드(혹은 임의의 다른 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식

▶모든 노드를 방문하고자 하는 경우에 이 방법을 선택

▶깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함

▶검색 속도 자체는 BFS에 비해서 느림

▶ 스택, 재귀함수로 구현

  ① 탐색 시작 노드를 스택에 삽입하고 방문처리

  ② 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

  ③ 위 과정을 수행할 수 없을때까지 반복

   - 노드 방문 시 방문(Visited)여부를 반드시 검사해야 한다. 아니면 무한 루프에 빠질 수 있음.

   - 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(Depth bound)를 사용.

   - 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모 노드로 돌아와서(back tracking), 부모 노드에 이전과는 다른 동작자를 적용하여 새로운 자식 노드를 생성.

  

 

2. BFS

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

루트 노드(혹은 다른 임의의 노드) 에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼ㄴ저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

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

▶ 큐를 이용해서 구현

  ① 탐색 시작 노드를 큐에 삽입하고 방문처리

  ② 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리

  ③ 위 과정을 수행할 수 없을때까지 반복

 

3. 시간 복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.

DFS, BFS 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

 

4. 문제 유형

① 그래프의 모든 정점을 방문하는 것이 중요한 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없습니다.

 

② 경로의 특정을 저장해두어야 하는 문제

   DFS 사용. ( BFS는 경로의 특징을 가지지 못함)

 

③ 최단거리 구하는 문제

  BFS 를 사용하는 것이 유리합니다.

 깊이 우선 탐색으로 경로를 검색할 경우, 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리가 됩니다.

 

④ 검색 대상 그래프가 큰 문제

   DFS

 

⑤ 검색 대상 그래프가 크지 않고, 검색 시작 지점부터 원하는 대상이 별로 멀지 않은 문제

   BFS