그래프를 탐색하는 방법
그래프?
정점(node)와 그 정점을 연결하는 간선(edge)로 구성된 자료구조의 일종
그래프를 탐색한다 = 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문한다.
깊이 우선 탐색(DFS, Depth-First-Search)
: 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 모든 노들르 방문하고자 하는 경우 이 방법을 선택
- 너비 우선 탐색에 비해서 조금 더 간단함
- 검색 속도 자체는 너비 우선 탐색에 비해서 느림
너비 우선 탐색(BFS, Breadth-First-Search)
: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 주로 두 노드 사이의 최단경로를 알고 싶을 때 이 방법을 선택
DFS : 스택 또는 재귀함수로 구현
BFS : 큐를 이용해서 구현
활용한 문제 유형/응용
1) 그래프의 모든 정점을 방문하는 문제
DFS, BFS 상관X
2) 경로의 특징을 저장해둬야하는 경우
ex. 각 정점에 숫자가 적혀있고, a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등 : DFS (BFS는 경로의 특징을 가지지 못함)
3) 최단거리를 구해야하는 문제
미로 찾기 등 최단거리를 구해야 할 경우 : **BFS
+) 검색 대상의 그래프가 정말 크다면 DFS를 고려,
+) 검색 대상의 규모가 크지 않고, 검색 시작 점으로부터 원하는 대상이 별로 멀지 않다면 BFS
DFS (in Java)
BFS (in Java)
