[Algorithm] BFS & DFS

코딩 테스트를 대비하여 자료구조와 알고리즘에 대해 정리하며 공부중입니다.
틀린 부분이 있을 수 있다는 점을 감안하고 봐주시기 바라며, 지적은 언제나 환영합니다.

BFS, DFS

그래프를 탐색하는 방법에는 크게 너비 우선 탐색(BFS) 과 깊이 우선 탐색(DFS) 이 있다.

---

그래프(Graph)

• 정의 : Node(정점, vertex) 와 그 Node들을 연결하는 Edge(간선) 을 하나로 모아놓은 자료 구조.
• Node(정점) : 그래프의 특정 위치라는 개념으로 사용한다.
  • 트리(Tree)구조와 다르게, Root node의 개념이 없다.
• Edge(간선) : Node간의 관계를 연결하는 선.
  • 두 그래프의 Node의 갯수가 같아도, Edge의 갯수는 다를 수 있다. (Edge가 없을 수도 있다.)
• 그래프의 탐색 : 그래프의 최초 Node로부터 시작하여, 모든 Node를 순서대로 방문하는 것을 말함.

---

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

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

• 루트 Node(혹은 다른 임의의 Node)에서 시작해서 인접한 Node를 먼저 탐색하는 방법으로,
  시작 Node로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법.
• 주로 최단 경로를 찾고 싶을 때 BFS를 선택한다.
• Queue를 이용하여 구현한다.
  1. 탐색을 시작하는 루트 Node를 방문 예정 Queue에 삽입.
  2. Queue에서 Node를 꺼낸 뒤에 방문 처리.
  3. 해당 Node의 인접 Node 중 방문하지 않은 Node를 모두 방문 예정 Queue에 삽입.
  4. 더 이상 2~3번의 과정을 수행할 수 없을 때까지 반복.

장점

• 출발 Node에서 목표 Node까지의 최단 길이 경로를 보장한다.
  • 현재 Node에서 가까운 곳부터 찾기 때문에, 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문.

단점

• 경로가 매우 길 경우(목표 Node가 깊은곳에 있는 경우)에는 탐색 가지수가 급격히 증가함에 따라 보다 많은 기억 공간을 필요.
  • 공간 복잡도가 증가한다.

---

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

- 최대한 깊게 이동한 다음, 더 이상 갈 수 없을 때 옆으로 이동.

• 루트 Node(혹은 다른 임의의 Node)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.
• 주로 모든 Node를 방문하고자 할 때 DFS를 선택한다.
• 재귀함수나 Stack을 이용하여 구현한다.
  1. 탐색 시작하는 루트 Node를 방문 완료 Stack에 삽입.
  2. Stack의 최상단 Node에 방문하지 않은 인접한 Node가 하나라도 있으면, 그 Node를 Stack에 삽입.
  3. Stack의 최상단 Node에 대해, 방문하지 않은 인접 Node가 없으면 최상단 Node를 pop.
  4. 더 이상 2~3번의 과정을 수행할 수 없을 때까지 반복.

장점

• 단지 현 경로상의 Node만을 기억하면 되므로, 저장공간의 수요가 비교적 적다.
  • 공간 복잡도 측면에서 유리하다.

단점

• 해가 없는 경로에 깊이 빠지게 될 수록 탐색 시간이 증가한다.
  • 시간 복잡도 측면에서 불리하다.
• 반드시 최적해를 얻을 수 있다고 보장할 수 없다.
  • 해를 찾으면 탐색을 끝내버리기 때문에, 목표에 이르는 경로가 다수인 문제인 경우에는 최적해를 보장할 수 없다.

---

BFS vs DFS

	BFS	DFS
탐색 방법	현재 Node에 연결된 가까운 Node들부터 탐색	현재 Node에서 갈 수 있는 Node들까지 들어가면서 탐색
구현	Queue를 이용해서 구현	Stack 또는 재귀함수로 구현
검색 속도	비교적 빠름	비교적 느림
시간 복잡도 (모든 인접 Node를 방문할 때)	인접행렬: O(N^2) / 인접리스트 : O(N+E)	인접행렬: O(N^2) / 인접리스트 : O(N+E)
선택 기준	검색 대상 그래프의 규모가 작을 때 최단거리를 구해야 할 때	검색 대상 그래프의 규모가 클 때 경로마다의 특징을 저장해둬야 할 때