DFS(깊이우선탐색), BFS(너비우선탐색)

그래프와 트리

그래프(graph)

정점(node)과 그 정점을 연결하는 간선(edge)로 이루어진 자료구조의 일종
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

트리

아주 간단한게만 말하자면, 그래프 중에서 방향성이 있는 비순환 그래프

• 그래프의 탐색의 목적은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이다.
• 그래프의 데이터는 배열처럼 정렬이 되어 있지 않다.
• 그래프에서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.

❗️그래프의 모든 정점 탐색 방법

지하철 노선도 애플리케이션에서 경로를 탐색할 때, 최단 경로나 최소 환승 등 하나의 목적에도 여러 가지 방법이 있다.
그래프의 모든 정점 탐색 방법에도 여러 가지가 있다.
그중에서 가장 대표적인 두 가지 방법, DFS와 BFS를 알아보자.

이 둘은 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다.

DFS(깊이우선탐색)

루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 아래로 깊이있게 탐색하는 방식.

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

BFS(너비우선탐색)

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방식.

1. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
2. 주로 두 노드 사이의 ⭐️최단 경로⭐️를 찾을 때 사용한다.

DFS, BFS의 시간 복잡도

두 반식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
N=노드, E=간선 일 때,

• 인접 리스트 : O(N+E)
• 인접 행렬 : O(N^2)

일반적으로 간선(E)의 크기가 N^2에 비해 상대적으로 적기에 인접 리스트 방식이 효율적이다.

왜 DFS는 최단경로를 보장못해?

예를 들어, A와 B사이의 거리를 구해야 한다. 두 가지 방식으로 했을 때의 차이?

DFS : A부터 B까지 모든 경로를 다 봐야 한다.
BFS : A와 가까운 곳부터 탐색을 시작한다.

DFS는 하나의 정점에서 계속 파고든다. 가까운 한명에서 계속 파고들어서 아니면 다시 돌아가!! 이런 개념
BFS는 나랑 연결된 애들은 일단 다 본다. 없으면 걔네랑 또 연결된 애들 본다!

그러니 최단 경로라는 문제에서 DFS는 최적해를 보장 못하는 게 맞다!

DFS, BFS 활용한 문제 유형

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순 모든 정점 방문이라면 DFS, BFS 어느 것을 사용해도 상관없다.

2) 경로의 특징을 저장해둬야 하는 문제
각 정점에 숫자가 적혀있고 a~b까지 가는 경로를 구하는 데, 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 갖지 못한다)

3) 최단 거리를 구해야 하는 문제
미로 찾기 등, 최단 거리 일때는 BFS가 유리하다.
DFS의 경우, 처음 발견되는 답이 최단 거리가 아닐 수도 있지만 BFS는 너비 우선으로 찾기때문에 최단 거리를 여러개 받아서 Math.min()으로 비교해서 구해줄 수 있따.

+) 검색 대상 그래프가 정말 크다면 DFS
+) 검색 대상 규모가 크지 않고, 검색 시작 시점으로부터 원하는 대상이 별로 멀지 않다면 BFS

참고

https://hanamon.kr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%83%90%EC%83%89-bfs-dfs/
https://velog.io/@jaeyunn_15/알고리즘-DFS깊이우선탐색-BFS너비우선탐색