DFS(Depth-First Search)와 BFS(Breadth-First Search) 모두 대표적인 그래프에서 모든 정점을 방문하기 위한 탐색법이다.

그래프란?

그래프는 정점과 간선을 통해 자료를 표현하는 방식이다.
정점(Vertex)은 대상 및 개체를 나타낸다.
간선(Edge)은 정점간의 관계를 나타낸다.
간선은 방향성을 가질 수 있으며, 가중치를 가질 수도 있다.

DFS, 깊이 우선 탐색

직관적인 이해를 위해 트리를 기준으로 DFS가 설명된 이미지를 가져왔다.

DFS는 루트를 기준으로 루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳까지 내려간다. 더 이상 내려갈 수 없는 경우, 올라오다가 내려갈 수 있는 곳이 다시 보인다면 내려가는식으로 탐색한다.

즉 루트 노드에서 시작해 다음 분기로 넘어가기 전까지, 해당 분기를 완벽하게 탐색하는 방법 이라고 설명할 수 있다.

위와 같은 이유로 BFS(깊이 우선 탐색)이라고 불린다.

DFS의 특징

• 자기 자신을 호출하는 재귀 순한의 형태를 띔.
• 단순 검색 속도는 BFS에 비해 느림.
• 노드 방문 여부를 반드시 검사해야한다.
  - 그렇지 않으면 무한하게 노드를 순환하게 된다.

DFS의 탐색 과정

출처: https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

DFS의 구현

1. 재귀 호출 구현방법
2. 명시적 스택 사용: 방문 정점을 스택에 저장 후 꺼내서 작업

PS에서의 DFS

• 미로, 지도 등의 탐색
• 전체를 방문하는데 걸리는 횟수 등 유형의 문제

참고자료
https://takeitoutamber.medium.com/binary-tree-right-side-view-bfs-87a215b6237c
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html