그래프(graph)
- 정점(node)과 그 정점을 연결하는 간선(edge)로 이루어진 자료구조의 일종
- 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
트리
아주 간단한게만 말하자면, 그래프 중에서 방향성이 있는 비순환 그래프
DFS(깊이우선탐색)
- 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함.
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단.
- 검색 속도 자체는 너비 우선 탐색에 비해 느리다.
BFS(너비우선탐색)
- 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
주로 두 노드 사이의 ⭐️최단 경로⭐️를 찾을 때 사용한다.
DFS & BFS
🧐 A와 B사이의 거리를 구해야 한다. 두 가지 방식으로 했을 때의 차이?
- DFS : A부터 B까지 모든 경로를 다 봐야 한다.
- BFS : A와 가까운 곳부터 탐색을 시작한다.
그렇지 않을까?
DFS는 하나의 정점에서 계속 파고든다. 가까운 한명에서 계속 파고들어서 아니면 다시 돌아가!! 이런 개념
BFS는 나랑 연결된 애들은 일단 다 본다. 없으면 걔네랑 또 연결된 애들 본다!
그러니 최단 경로라는 문제에서 DFS는 최적해를 보장 못하는 게 맞다!
DFS, BFS의 시간 복잡도
- 두 반식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
N=노드, E=간선 일 때,
- 인접 리스트 : O(N+E)
- 인접 행렬 : O(N^2)
일반적으로 간선(E)의 크기가 N^2에 비해 상대적으로 적기에 인접 리스트 방식이 효율적이다.
DFS, BFS 활용한 문제 유형
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순 모든 정점 방문이라면 DFS, BFS 어느 것을 사용해도 상관없다.
2) 경로의 특징을 저장해둬야 하는 문제
각 정점에 숫자가 적혀있고 a~b까지 가는 경로를 구하는 데, 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 갖지 못한다)
3) 최단 거리를 구해야 하는 문제
미로 찾기 등, 최단 거리 일때는 BFS가 유리하다.
DFS의 경우, 처음 발견되는 답이 최단 거리가 아닐 수도 있지만 BFS는 너비 우선으로 찾기때문에 최단 거리를 여러개 받아서 Math.min()으로 비교해서 구해줄 수 있따.
+) 검색 대상 그래프가 정말 크다면 DFS
+) 검색 대상 규모가 크지 않고, 검색 시작 시점으로부터 원하는 대상이 별로 멀지 않다면 BFS
