💡 DFS vs BFS 한 눈에 보기

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

• 각 정점 노드를 깊게 탐색하는 방식으로 매 탐색을 stack으로 쌓으면서 갈 수 있는 최대한 깊이를 탐색하고 갈 곳이 없다면 이전 정점으로 돌아간다.
• 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
• 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

깊이 우선 탐색(DFS)의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. → 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
  

깊이 우선 탐색(DFS)의 구현

1. 순환 호출 이용

2. 명시적인 스택 사용

   → 명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업한다.

DFS와 BFS 한 눈에 이해하기

DFS의 탐색 과정

→ DFS의 기본 탐색 과정은 특정 정점에서 시작하여 역추적(backtracking) 하기 전에 각 분기를
따라 가능한 한 멀리 탐색하는 것이다. 탐색하는 과정은 다음과 같다.

1. 현재 노드를 방문한 것으로 표시한다.
2. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색한다.
3. 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking) 한다.
4. 모든 정점을 방문할 때까지 프로세스를 반복한다.

DFS의 장단점

DFS의 장점

1. DFS는 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
2. DFS는 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.
3. DFS를 사용하여 그래프에서 순환을 감지할 수 있다.

DFS의 단점

1. 순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
2. DFS는 두 정점 사이의 최단 경로를 찾으려는 경우 사용하기에 최고의 알고리즘이 아닐 수 있다.

• DFS는 특정 시나리오에서 매우 유용할 수 있지만 항상 최선의 선택은 아니다.
• 해결하려는 특정 문제에 따라 다른 알고리즘이 더 적합할 수 있다.