(자료구조,알고리즘) BFS / DFS

BFS(Breadth-First Search)

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

너비 우선 탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
ex) 지구 상에 존재하는 모든 자동차를 그래프로 표현한 후 taycan과 AMG사이에 존재하는 경로를 찾는 경우

• 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
• 너비 우선 탐색의 경우 - taycan과 가까운 관계부터 탐색

DFS(Depth-First Search)

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

깊이 우선 탐색의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에
해당 분기를 완벽하게 탐색하는 방식을 말한다.

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

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